【模拟7.14】建造游乐园(play)

这题是玄学的数论

首先考虑如何枚举偶数点度的图

可以考虑取出i-1个点那么成图的数量为2^C(i-1,2)

(原因单独取出的i点能平衡已建图中的奇数点，原因是某种性质。。。。)

然后求带联通标号的欧拉图

$f_{i}$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<cmath>
 8 #include<bits/stdc++.h>
 9 #include<stack>
10 #include<queue>
11 #include<set>
12 #define MAXN 1000001
13 #define ps push_back 
14 #define pt printf("--------
");
15 #define ll long long 
16 using namespace std;
17 const ll mod=1e9+7;
18 ll g[MAXN],f[MAXN];
19 ll jie[MAXN],ni[MAXN],ni_c[MAXN];ll n;
20 ll pow(ll x,ll y)
21 {
22     ll ans=1;
23     while(y){
24        if((y&1)==1)ans=(ans*x)%mod;
25        x=(x*x)%mod;
26        y>>=1;
27     }
28     return ans%mod;
29 }
30 ll C(ll x,ll y)
31 {
32    if(y>x)return 0;return (jie[x]*ni_c[y]%mod*ni_c[x-y]%mod+mod)%mod;
33 }
34 int main()
35 {
36     scanf("%lld",&n);
37     jie[1]=1;jie[0]=1;ni[1]=1;ni_c[1]=1;ni_c[0]=1;ni[0]=1;
38     for(ll i=2;i<=n;++i){
39        jie[i]=(jie[i-1]*i)%mod;
40        ni[i]=((mod-mod/i)*ni[mod%i])%mod;
41        ni_c[i]=(ni_c[i-1]*ni[i])%mod;
42     }
43     g[1]=1;
44     for(ll i=2;i<=n;++i){
45         g[i]=pow(2ll,C(i-1ll,2ll))%mod;
46        // printf("C=%lld g[%lld]=%lld
",C(i-1,2ll),i,g[i]);
47     }
48     f[1]=1;
49     for(ll i=2;i<=n;++i)
50     {
51         f[i]=(f[i]+g[i])%mod;
52         for(ll j=1;j<=i-1;++j)
53         {
54            f[i]=(f[i]-(f[j]*g[i-j]%mod*C(i-1ll,j-1ll)%mod)+mod)%mod;
55            //printf("f[%lld]=%lld g[%lld]=%lld
",j,f[j],i-j,g[i-j]);
56         }
57         f[i]%=mod;
58         //printf("f[%lld]=%lld
",i,f[i]);
59     }
60     printf("%lld
",(f[n]*C(n,2)+mod)%mod);
61 }

View Code