HZOI2019建造游乐园（play）组合数学，欧拉图

题目：https://www.cnblogs.com/Juve/articles/11186805.html（密码是我的一个oj用户名）

solution：

反正我是想不出来。。。

题目大意就是要求出有多少个图删除一条边或加上一条边后成为一个连通的欧拉图

实际上答案等于有n个点的带标号连通的欧拉图数量*$C_{n}^{2}$，也就是我先数出所有的欧拉图数量，在这个欧拉图上删一条边或是加一条边得到合法方案，那么其实每一条边只会对应删或加，及$C_{n}^{2}$中选择。

数连通欧拉图则可以用容斥原理解决。

设连同欧拉图个数为f_i，所有点度数均为偶数的图（不一定连通）为g_i

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

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

组合数可以杨辉三角也可以求逆元

复杂度n²

杨辉三角版：

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

#define mod 1000000007

#define MAXN 4002

using namespace std;

ll n,g[MAXN],f[MAXN],C[MAXN][MAXN];

ll q_pow(ll a,ll b,ll p){

	ll ans=1;

	for(;b;b>>=1){

		if(b&1) ans=ans*a%p;

		a=a*a%p;

	}

	return ans%mod;

}

int main(){

	scanf("%lld",&n);

	for(ll i=0;i<=n+1;i++){

		C[i][0]=1;

		for(ll j=1;j<=i;j++)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

	}

	//for(ll i=1;i<=n;i++)

	//	for(ll j=1;j<i;j++)

	//		cout<<C[i][j]<<endl;

	for(ll i=1;i<=n;i++){

		f[i]=g[i]=q_pow(2,C[i-1][2],mod)%mod;

		for(ll j=1;j<i;j++){

			f[i]=(f[i]-f[j]*g[i-j]%mod*C[i-1][j-1]%mod+mod)%mod;

		}

	}

	printf("%lld\n",f[n]*C[n][2]%mod);

	return 0;

}

逆元版：

 #include<cstdio>

 #define p 1000000007

 using namespace std;

 int n;

 long long g[],f[],fac[];

 inline long long qpow(long long a,long long b){register long long ans=;a%=p;while(b){if(b&)ans=ans*a%p;a=a*a%p;b>>=;}return ans;}

 inline long long C(long long nn,long long k){if(k>nn)return ;else return fac[nn]*(qpow(fac[k]*fac[nn-k]%p,p-))%p;}

 inline long long Lucas(long long a,long long b){if(b==) return ;return C(a%p,b%p)*Lucas(a/p,b/p)%p;}

 inline void getchart(){fac[]=fac[]=;for(register long long i=;i<=n;i++) fac[i]=(fac[i-]*i)%p;return ;}

 int main()

 {

     scanf("%d",&n);getchart();

     for(register int i=;i<=n;++i)g[i]=qpow(,Lucas(i-,))%p;

     for(register int i=;i<=n;++i)

     {

         long long ll=;

         for(register int j=;j<=i;++j)

             ll=(ll+((f[j]*g[i-j]%p)*Lucas(i-,j-)%p))%p;

         f[i]=((g[i]-ll)%p+p)%p;

     }

     long long ans=f[n]*Lucas(n,)%p;

     printf("%lld",ans);

     return ;

 }

Joe太巨了

当然你可以打表：

 #include<cstdio>

 const long long L=<<|;

 char buffer[L],*S,*TT;

 #define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,L,stdin),S==TT))?EOF:*S++)

 inline int read()

 {

     register int a=,b=;

     register char ch=getchar();

     while(ch<''||ch>'')b=(ch=='-')?-:,ch=getchar();

     while(ch>=''&&ch<='')a=(a<<)+(a<<)+(ch^),ch=getchar();

     return a*b;

 }

 int ans[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

 signed main()

 {

     int n;n=read();

     printf("%d",ans[n]);

     return ;

 }

soul受我一拜

巴特西

HZOI2019建造游乐园（play）组合数学，欧拉图

最新文章

热门文章