1089: [SCOI2003]嚴格n元樹

Time Limit:?1 Sec??Memory Limit:?162 MB
Submit:?1899??Solved:?954
[Submit][Status][Discuss]

Description

　　如果一棵樹的所有非葉節點都恰好有n個兒子，那么我們稱它為嚴格n元樹。如果該樹中最底層的節點深度為d
（根的深度為0），那么我們稱它為一棵深度為d的嚴格n元樹。例如，深度為２的嚴格２元樹有三個，如下圖：

　　給出n, d，編程數出深度為d的n元樹數目。

Input

　　僅包含兩個整數n, d( 0?? <?? n?? <?? =?? 32,?? 0? < =?? d? < = 16)

Output

　　僅包含一個數，即深度為d的n元樹的數目。

Sample Input

【樣例輸入1】
2 2

【樣例輸入2】
2 3

【樣例輸入3】
3 5

Sample Output

【樣例輸出1】
3

【樣例輸出2】
21

【樣例輸出2】
58871587162270592645034001 /* 定義S[i]代表深度<=i的嚴格n元樹的個數 那么最后S[d]-S[d-1]就是答案 那么對于S[i]，我們由S[i-1]遞推來， 我們考慮新加一個根節點，然后根節點有n個子節點，每個子節點都可以建一顆深度<=i-1的樹，那么每個 子節點都有S[i-1]種選法，那么n個子節點就有S[i-1]^n選法，再加上都不選，就是深度為0的情況 那么S[i]:=（S[i-1]^n）+1； */ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<iomanip> using namespace std; struct long_int{int num[3000],cnt;void operator = (int y){num[1]=y;cnt=1;}int& operator [] (int x){return num[x];} }S[200]; void operator *= (long_int &x,long_int &y) {long_int z=S[199];int i,j;for(i=1;i<=x.cnt;i++)for(j=1;j<=y.cnt;j++){z[i+j-1]+=x[i]*y[j];z[i+j]+=z[i+j-1]/10000;z[i+j-1]%=10000;}z.cnt=x.cnt+y.cnt;if(!z[z.cnt])--z.cnt;x=z; } void operator ++ (long_int &x) {int i=1;x[1]++;while(x[i]==10000)x[i]=0,x[++i]++; } long_int operator - (long_int &x,long_int &y) {long_int z=S[199];int i;for(i=1;i<=x.cnt;i++){z[i]+=x[i]-y[i];if(z[i]<0) z[i]+=10000,z[i+1]--;if(z[i]) z.cnt=i;}return z; } long_int operator ^ (long_int x,int y) {long_int z=S[199];z=1;while(y){if(y&1) z*=x;x*=x;y>>=1;}return z; } ostream& operator << (ostream &os,long_int x) {int i;os<<x[x.cnt];for(i=x.cnt-1;i;i--)os<<setfill('0')<<setw(4)<<x[i];//os<<x[i];return os; } int n,d; int main() {int i;cin>>n>>d;if(!d){puts("1");return 0;}S[0]=1;for(i=1;i<=d;i++)S[i]=S[i-1]^n,++S[i];cout<<S[d]-S[d-1]<<endl; }

?

?

?

轉載于:https://www.cnblogs.com/L-Memory/p/7528222.html

總結

以上是生活随笔為你收集整理的bzoj1089 [SCOI2003]严格n元树(dp+高精)的全部內容，希望文章能夠幫你解決所遇到的問題。

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