是我图论没学好，啊不对，应该说我小学奥数没学好，当时看见题里的欧拉路我就开始想这玩意的性质，画了满满一算草纸的图，也没得出什么结论来，最后手模了个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]-∑f[j]*C(i-1,j-1)*g[i-j]

我们来稍微感性的理解一下这个式子，你让j个点连通，那就剩下i-j个点随便连就好了，可是这样的话你会发现你减重了，因为可能你的j个点连通，i-j个点随便连，恰好构成了k个点连通，那怎么办呢？我们在j个点连通中固定出一个点来，这样的话肯定就不重了，这就是C(i-1,j-1)里面-1的来源

 

1 //无向图一定是有偶数个奇数度的点 2 #include
      
        3 #include
       
         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<<"计算错误"<