只要求出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);
}