[hdu5629]Clarke and tree

首先由一个神奇的序列叫做Purfer序列，他可以表示一棵树，且每个节点出现此时为度数-1(因此总长为n-2)。

然后dp，用f[i][j][k]表示用前i个点中的j个点构成了一个长度为k的Purfer序列（当然要符合条件），那么有$f[i][j][k]=f[i-1][j][k]+\sum\limits_{i=0}^{a[i]-1}f[i-1][j-1][k-l]\cdot c(k,l)$，可以类似背包的消掉i（j和k要倒序），然后递推即可。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 105

 4 #define mod 1000000007

 5 int t,n,a[N],f[N][N],c[N][N];

 6 int main(){

 7     for(int i=0;i<=100;i++)c[i][0]=c[i][i]=1;

 8     for(int i=2;i<=100;i++)

 9         for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;

10     scanf("%d",&t);

11     while (t--){

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

13         memset(f,0,sizeof(f));

14         f[0][0]=1;

15         for(int i=1;i<=n;i++)scanf("%d",&a[i]);

16         for(int i=1;i<=n;i++)

17             for(int j=i;j;j--)

18                 for(int k=n-2;k>=0;k--)

19                     for(int l=0;l<a[i];l++)

20                         f[j][k]=(f[j][k]+1LL*f[j-1][k-l]*c[k][l])%mod;

21         printf("%d ",n);

22         for(int i=2;i<n;i++)printf("%d ",f[i][i-2]);

23         printf("%d\n",f[n][n-2]);

24     }

25 }

巴特西

[hdu5629]Clarke and tree

最新文章

热门文章