[BZOJ1089][SCOI2003]严格n元树（递推+高精度）

=== ===

这里放传送门

=== ===

题解

这题是当时NOIP之前在openjudge上做题的时候看到的。。openjudge上把这个题已经弱化到极致了。。它说保证最底层节点不超过1024，那么一个很显然的思路就是可以往下面接儿子，每一个最底层节点都可以选择接或者不接这样。但是这里的原题没有这条限制，那么就不能考虑往下面接儿子了，可以选择往上面放父亲。对于一个作为根节点的点来说，它一共有n个儿子，其中至少有1个儿子是一个n-1层的树，其它可以任选。设1..i层的严格n元树的方案树总共为sum[i]，那么n个儿子的所有可能情况是 sum[n−1]n 。但是这里面还包括n个儿子中一个n-1层的也没有的情况，所以要减去 sum[n−2]n 这样就可以了。然而这题要写个高精快速幂还要压位这是最蛋疼的。。

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,d; const int wer=10000; struct number{ int s[300],len; void print(){ printf("%d",s[len]); for (int i=len-1;i>=1;i--){ if (s[i]/1000==0) printf("0"); if (s[i]/100==0) printf("0"); if (s[i]/10==0) printf("0"); printf("%d",s[i]); } } number(){memset(s,0,sizeof(s));len=0;} number operator = (const int &i){s[1]=i;len=1;} number operator + (const number &a){ number c; c.len=max(len,a.len); for (int i=1;i<=c.len;i++){ c.s[i]+=s[i]+a.s[i]; c.s[i+1]+=c.s[i]/wer; c.s[i]%=wer; } if (c.s[c.len+1]!=0) ++len; return c; } number operator * (const number &a){ number c; for (int i=1;i<=len;i++) for (int j=1;j<=a.len;j++){ c.s[i+j-1]+=s[i]*a.s[j]; c.s[i+j]+=c.s[i+j-1]/wer; c.s[i+j-1]%=wer; } c.len=len+a.len-1; while (c.s[c.len+1]!=0){ ++c.len; c.s[c.len+1]=c.s[c.len]/wer; c.s[c.len]%=wer; } return c; } number operator - (const number &a){ number c; c=*this; for (int i=1;i<=c.len;i++){ c.s[i]-=a.s[i]; if (c.s[i]<0){c.s[i]+=wer;c.s[i+1]-=1;} } while (c.s[c.len]==0) --c.len; return c; } }sum1,sum2,f,sumpow; number powww(number a,int t){ number ans; ans=1; while (t!=0){ if (t&1) ans=ans*a; a=a*a;t>>=1; } return ans; } int main() { scanf("%d%d",&n,&d); if (d<=1){printf("1\n");return 0;}//注意特判 sum1=2;sum2=1; sumpow=powww(sum2,n); for (int i=2;i<=d;i++){ number tmp=powww(sum1,n); f=tmp-sumpow; sumpow=tmp;//直接继承前面的结果，减少计算次数 sum1=sum1+f; } f.print(); return 0; }