Description

有n個點，它們從1到n進行標號，第i個點的限制為度數不能超過A[i].
現在對于每個s (1 <= s <= n)，問從這n個點中選出一些點組成大小為s的有標號無根樹的方案數。

Input

第一行一個整數n.
第二行n個整數表示A[i].

Output

輸出一行n個整數，第i個整數表示s=i時的答案。答案模1004535809 = 479 * 2^{21} + 1。

Sample Input

3
2 2 1

Sample Output

3 3 2

Data Constraint

20%的數據：n <= 6
60%的數據：n <= 50
100%的數據：n <= 100

Solution

• 首先我們要知道一棵無根樹的 prufer 數列與樹的形態一一對應。

• 對于 prufer 數列不知道的可以查看 morejarphone 大佬關于 Prufer 數列的詳細解釋

• 對于大小為 s 的樹，我們統計的是一個長度為 s?2 的序列。

• 而且可以發現一個點在 prufer 數列出現的次數加一就是它的度數。

• 所以度數不超過 Ai 即 i 在序列中的出現次數小于 Ai 。

• 若已知選出了 s 個點，且這些點的出現次數為 Ci ，則這些點組成一棵樹的方案數為：

  s!C1!?C2!?…?Cs!

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int N=101,mo=1004535809; int a[N]; long long f[N][N][N],g[N],h[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int min(int x,int y) {return x<y?x:y; } inline long long ksm(long long x,int y) {long long s=1;while(y){if(y&1) s=s*x%mo;x=x*x%mo;y>>=1;}return s; } int main() {int n=read();g[0]=h[0]=f[0][0][0]=1;for(int i=1;i<=n;i++) a[i]=read(),g[i]=g[i-1]*i%mo;h[n]=ksm(g[n],mo-2);for(int i=n-1;i;i--) h[i]=h[i+1]*(i+1)%mo;for(int i=0;i<n;i++)for(int j=0;j<=i;j++)for(int k=0;k<=n;k++)if(f[i][j][k]){f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%mo;//nofor(int l=0,p=min(n-k-2,a[i+1]-1);l<=p;l++)f[i+1][j+1][k+l]=(f[i+1][j+1][k+l]+f[i][j][k]*h[l]%mo)%mo;//yes}printf("%d",n);for(int i=2;i<=n;i++) printf(" %lld",f[n][i][i-2]*g[i-2]%mo);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5068. 【GDSOI2017第二轮模拟】树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。