题目:
分析:
好难好难。。。
下来听神仙讲。。
每一个长度为n-2的prufer序列一一对应一棵大小为n的树。。。
每个点在序列中的出现次数为该点的度数减一
哦???
。。。
哦。。。
prufer序列貌似忘得差不多了诶。。
于是问题就变成在长度为n-2的序列上放1~n,每个元素有次数限制。。。
n^4DP。。。100卡一卡就跑得过。。。
f [ i ] [ j ] [ k ]表示考虑前 i 个数,用了 j 个,一共占了prufer序列 k 个位置。。。
然后组合数加加减减。。。
还是自己太菜了
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<map> #define maxn 105 #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; inline int getint() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=num*10+c-48,c=getchar(); return num*flag; } int n; long long fac[maxn],inv[maxn]; int A[maxn],cnt; long long f[maxn][maxn][maxn]; int main() { int T=getint(); fac[0]=fac[1]=inv[0]=inv[1]=1; for(int i=2;i<maxn;i++)fac[i]=fac[i-1]*i%MOD; for(int i=2;i<maxn;i++)inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD; for(int i=2;i<maxn;i++)inv[i]=inv[i-1]*inv[i]%MOD; while(T--) { n=getint();cnt=0; for(int i=1;i<=n;i++)cnt+=((A[i]=getint())>0); memset(f,0,sizeof f);f[0][0][0]=1; for(int i=1;i<=n;i++)for(int j=0;j<i;j++)for(int k=0;k<=n-2;k++) { (f[i][j][k]+=f[i-1][j][k])%=MOD; for(int o=0;o<=min(n-k-2,A[i]-1);o++) (f[i][j+1][k+o]+=f[i-1][j][k]*inv[o]%MOD)%=MOD; } printf("%d",cnt); for(int i=2;i<=n;i++)printf(" %lld",f[n][i][i-2]*fac[i-2]%MOD); printf(" "); } }