是我图论没学好，啊不对，应该说我小学奥数没学好，当时看见题里的欧拉路我就开始想这玩意的性质，画了满满一算草纸的图，也没得出什么结论来，最后手模了个4，还没模对，就光荣暴零了
首先我们应该知道，无向图一定有偶数个奇数度的点，随便画，有反例算我输，那我们先不管连不连通，先搞个有欧拉路的图出来
问：怎么样就会有欧拉路？
答：只要这个图中所有点的度都为偶数，那这个图就一定是个欧拉路，当然了，可能连通也可能不连通
我们设g[i]表示i个点构成的不知道是不是连同的欧拉路，那么
$g[i]=2^{C_{i-1}^2}$
这个式子可以这么来理解，我在i-1个点中选2个点，随便连边或者不连边，我就得到了一个有i-1个点的无向图，为什么是i-1个点呢？因为我要留出一个点来平衡这个图，说是平衡，其实就是把一个普通的无向图搞成欧拉路，怎么搞呢？这个时候这i-1个点构成的
无向图一定有偶数个需要被连边变成偶数度的点，那就让留出来的点和需要被连边的点连边啊，这样一搞，奇数度的点就变成偶数度了，留出来的这个点也肯定连了偶数条边，那不就是个欧拉路了嘛
现在我们需要做的是把不连通搞成连通，怎么搞？这i个点不连通里肯定包含了2个点连通剩下的不连通，3个点连通剩下的不连通…，看到这有没有想到些什么？我们可以容斥啊，我们把小于i个点的连通都干掉，那剩下的就是i个点全部连通，设f[i]代表i个点全部连通的欧拉路，那么
$f[i]=g[i]-{sum}f[j]{ imes}C_{i-1}^{j-1}{ imes}g[i-j]$
我们来稍微感性的理解一下这个式子，你让j个点连通，那就剩下i-j个点随便连就好了，可是这样的话你会发现你减重了，因为可能你的j个点连通，i-j个点随便连，恰好构成了k个点连通，那怎么办呢？我们在j个点连通中固定出一个点来，这样的话肯定就不重了，这就是$C_{i-1}^{j-1}$里面-1的来源
1 //无向图一定是有偶数个奇数度的点 2 #include<iostream> 3 #include<cstdio> 4 #define maxn 2010 5 #define ll long long 6 using namespace std; 7 const long long mod=1e9+7; 8 int n; 9 ll C[maxn][maxn]; 10 ll g[maxn],f[maxn]; 11 ll ksm(int x,ll b,ll c) 12 { 13 ll ans=1,a=(ll)x; 14 a=a%c; 15 while(b>0) 16 { 17 if(b&1) ans=(ans*a)%c; 18 b=b>>1; a=(a*a)%c; 19 } 20 return ans%c; 21 } 22 int main() 23 { 24 scanf("%d",&n); 25 for(int i=0;i<=n;++i) 26 { 27 C[i][0]=1; 28 for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; 29 } 30 for(int i=1;i<=n;++i) 31 { 32 int ls=((i-1)*(i-2))/2;//<==>C(i-1,2) 33 ll mi=(ll)ls; 34 g[i]=ksm(2,mi,mod);//每个点可连可不连 35 ll L=ksm(2,C[i-1][2],mod); 36 if(L!=g[i]) cout<<"计算错误"<<endl; 37 } 38 for(int i=1;i<=n;++i) 39 { 40 f[i]=g[i]; 41 for(int j=1;j<=i-1;++j) 42 f[i]-=((f[j]*C[i-1][j-1])%mod*g[i-j])%mod; 43 f[i]=f[i]%mod; 44 } 45 /*for(int i=1;i<=n;++i) cout<<g[i]<<" "; 46 cout<<endl;*/ 47 ll ans=(f[n]*C[n][2])%mod; 48 if(ans<0) ans+=mod; 49 printf("%lld ",ans); 50 return 0; 51 }