数学+图论 建造游乐场

xiaoxiao2021-02-28  15

只要求出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); }
转载请注明原文地址: https://www.6miu.com/read-450069.html

最新回复(0)