PE677 Coloured Graphs

题目描述

求n个点的无标号无根树的个数，每个点为红蓝黄三种颜色之一，满足红点的度数<=4，蓝黄点度数<=3，并且不能有两个黄点相连，模1e9+7

n=10000

题解

无标号无根树计数，在重心处统计，每次加上当前最大的子树即可

code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define mod 1000000007
#define Mod 1000000005
#define ll long long
#define file
using namespace std;

ll w[5],f[10001][3][5],g[10001][3],ans;
int n,N,i,j,k,l,J;

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}
ll C(ll n,int m) {ll ans=1;int i; fo(i,1,m) ans=ans*w[i]%mod*(n-i+1)%mod;return ans;}

int main()
{
	#ifdef file
	freopen("PE677.in","r",stdin);
	#endif
	
	scanf("%d",&n);N=n/2;
	f[1][0][0]=f[1][1][0]=f[1][2][0]=1;
	w[1]=1;
	fo(i,2,4) w[i]=mod-w[mod%i]*(mod/i)%mod;
	
	g[1][0]=g[1][1]=g[1][2]=1;
	fo(k,1,N)
	{
		fd(i,n,k)
		{
			fo(l,1,4)
			if (k*l<=i)
			{
				fo(j,l,4)
				{
					add(f[i][0][j],f[i-k*l][0][j-l]*C(g[k][0]+g[k][1]+g[k][2]+l-1,l));
					add(f[i][1][j],f[i-k*l][1][j-l]*C(g[k][0]+g[k][1]+g[k][2]+l-1,l));
					add(f[i][2][j],f[i-k*l][2][j-l]*C(g[k][0]+g[k][1]+l-1,l));
				}
			}
		}
		
		fo(i,1,n)
		{
			fo(j,0,2)
			{
				g[i][j]=0;J=(!j)?4:3;
				fo(l,0,J-1)
				add(g[i][j],f[i][j][l]);
			}
		}
	}
	
	fo(i,0,2)
	{
		k=(!i)?4:3;
		fo(j,0,k)
		add(ans,f[n][i][j]);
	}
	if (!(n&1)) add(ans,-g[N][0]*g[N][1]-g[N][0]*g[N][2]-g[N][1]*g[N][2]-C(g[N][0],2)-C(g[N][1],2));
	printf("%lld
",(ans+mod)%mod);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}