Orz 出题人

我们可以先求出有n个点的联通欧拉图数量，然后使它删或增一条边得到我们要求的方案

也就是让它乘上$C_n^2$ (n个点里选2个点，要么删边要么连边，选择唯一)

那么接下来就是求有n个点的联通欧拉图数量$f[n]$

首先来看欧拉图的定义：

一张无向图为欧拉图，当且仅当无向图连通，并且每个点的度数都是偶数。

那么设共有n个点且所有点度数皆为偶数的方案数为$g[n]$

之后尝试计算出来它

先把一个点拿出来，剩$n-1$个点

从这$n-1$个点中选2个点，这两点之间可以连或不连边

那么如果最终某个点的度数不为偶，就用之前单拿出来的点向他连边

 

最后有一个问题：如果单拿出来的点度数不为偶呢？

显然不可能。每条边对总度数的贡献为2，所以无重边无自环的话一定满足要求

可得

$g_i=2^{C_{i-1}^2}$

接下来应当让$g$中的方案保证联通即为$f$

正如上场T3一样，考虑总-目标之外

枚举$j=1->i-1$ 得到$f_j$是一部分点满足欧拉图性质的方案数

则$g_{i-j}$是剩下点满足度数为偶的方案数

我们现在要构造除了所求之外的情况，所以从那i个点里拿出一个，从剩下的里面选$j-1$个点连边

$f_i=g_i-\sum \limits_{j=1}^{i-1}{f_j*g_{i-j}*C_{i-1}^{j-1}}$

 

 

#include
     
      #include
      
       #include
       
        using namespace std;const int mod=1e9+7;typedef long long ll;int n;ll qpow(ll a,ll b){    ll res=1;    a%=mod;    while(b)    {        if(b&1)res=(res*a)%mod;        a=(a*a)%mod;        b>>=1;    }    return res%mod;}ll C[2005][2005],g[2005],f[2005];int main(){    scanf("%d",&n);    C[0][0]=1;    for(int i=1;i<=n;i++)    {        C[i][0]=1;        for(int j=1;j<=n;j++)            C[i][j]=C[i-1][j]+C[i-1][j-1],C[i][j]%=mod;    }//    while(1);    for(int i=1;i<=n;i++)        g[i]=qpow(2,C[i-1][2]);    for(int i=1;i<=n;i++)    {        f[i]=g[i];        for(int j=1;j<=i-1;j++)            f[i]=(f[i]-f[j]*g[i-j]%mod*C[i-1][j-1]%mod+mod)%mod;    }    cout<
        
         <