只要求出n个点能构成多少个不同的欧拉图即可。然后搞每两个点（对其增加或减少一条边）即有C(n,2)×f[n]个方案. 设n个点不重复的欧拉图个数为f[n]，设所有点度数均为偶数（但不一定联通）的图的个数为g[n]. g[i]=2^C(i-1,2).刨去一个点，其他点对之间可连可不连一条边的总方案数。但方案中一定有些点的度数是奇数，而刚刚刨掉的点就派上了用场，那个点有唯一一种方案使图中所有度数为奇数的点改变。 那么这个神奇的点的度数会不会变成奇数？ 答案当然是否定的。图中不可能有奇数个点的度数是奇数。因为每连一条边，对整张图度数的贡献是2，所以总的度数是偶数，而有奇数个点的度数是奇数则不满足。所以只可能有偶数个点度数是奇数，那么那个神奇点的度数也就一定是偶数（间接证明只有一种连接方式）。 欧拉图个数=总的图的个数-不满足的图的个数。 f[i]=g[i]-∑（1=< j<=i-1）f[j]*g[i-j]*C(i-1,j-1). 那么我来解释一下。。 单独拎出一个点（算作为起点），之后枚举出j-1个点，使这j个点作为一个联通欧拉图，而其他i-j点则不与这个联通欧拉图连接，共有g[i-j]个方案。 然后算算就行了。。
#pragma GCC optimize("O3") #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000007 #define ll long long using namespace std; ll n,f[2005],g[2005],C[2005][2005]; ll cheng(ll x,ll m) { ll ans=1; while(m) { if(m&1)ans=ans*x%mod; x=x*x%mod; m/=2; } return ans; } void init() { for(int i=0;i<=n;i++) { C[i][0]=1; for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } f[1]=g[1]=1; for(ll i=2;i<=n;i++)g[i]=cheng(2,C[i-1][2]); for(int i=2;i<=n;i++) { ll ans=0; for(int j=1;j<i;j++) { ll k=(f[j]*g[i-j]%mod)*C[i-1][j-1]%mod; ans=(ans+k)%mod; } f[i]=g[i]-ans; if(f[i]<0)f[i]+=mod; } } int main() { cin>>n; init(); printf("%lld",f[n]*C[n][2]%mod); }