Cptraser/ 三月 5, 2019/ 2019.3/ 0 comments

求加减一条边后点数为n的无向联通图欧拉回路图的个数,对1e9+7取模

f_i表示点数为点数为i的连通图欧拉回路图的个数,g_i表示点数为i随便你联不联通的欧拉回路图的个数。

由欧拉回路的性质可得:

    \[g_{i}=2^{C_{n-1}^{2}}\]

此处的意思是留一个点保证剩下点的度数都为偶数,所以剩下的点可以随意连边。

然后可得:

    \[f_{i}=g_i-\sum_{j=1}^{i-1}f_{j} * g_{i-j} * C_{i-1}^{j-1}\]

此处为了不出现重复的情况,固定一个点在连通图内,同时将剩下的点划分为两部分,一部分为点数为j的连通图,剩下的为一部分。由于此处方案数的有序性,乘以从i-1个点内选出j-1个点的方案数。(因为控住了一个点)。

#include <cstdio>
using namespace std;

const int Mod=1e9+7;

long long N;
long long Fac[2005],g[2005],f[2005],Inv[2005];
long long Ksm(long long x,long long y){long long res=1;for(;y;y>>=1,x=x*x%Mod)if(y&1)res=res*x%Mod;return res;}
long long C(int x,int y){if(x<y)return 0;return Fac[x]*Inv[y]%Mod*Inv[x-y]%Mod;}

void Mo(long long &x){if(x>=Mod)x%=Mod;}

int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    scanf("%lld",&N);Fac[0]=Fac[1]=1;
    for(long long i=2;i<=N;i++)Fac[i]=Fac[i-1]*i%Mod;
    for(int i=0;i<=N;i++)Inv[i]=Ksm(Fac[i],Mod-2);
    for(long long i=1;i<=N;i++)g[i]=Ksm(2,C(i-1,2));
    for(int i=1;i<=N;i++){
        for(int j=1;j<i;j++){
            Mo(f[i]+=f[j]*g[i-j]%Mod*C(i-1,j-1)%Mod);
        }f[i]=(g[i]-f[i]+Mod)%Mod;
    }printf("%lld",f[N]*C(N,2)%Mod);
    return 0;
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*