经典的Dp+前缀和
减法没有判断最改为是否为0 WA 了好久。。。
/************************************************************** Problem: 1089 User: lxy8584099 Language: C++ Result: Accepted Time:76 ms Memory:1144 kb****************************************************************/ /* 尝试 long double 能不能水过 看样子是不行的 f i 表示深度不超过i的n元树个数 假设我们已知f[i-1]，那么深度不大于i的树就相当于多出了一个根节点， 其每一个儿子(共n个儿子)都是一颗深度不大于i-1的树。 f i = f i-1 ^n +1 1 表示只有一个节点的情况 答案就是 f n - f n-1 */#include#include using namespace std;const int N=1e4+50;struct Mat{ int m[N],l; Mat() { memset(m,0,sizeof(m)); l=0; } Mat operator + (int b) { Mat a=*this; int p=1;a.m[p]+=b; while(a.m[p]>=10) { int k=a.m[p]/10; a.m[p]%=10; a.m[++p]+=k; } a.l+=5; while(a.m[a.l]==0) a.l--; return a; } Mat operator - (Mat b) { Mat a=*this; for(int i=1;i<=a.l;i++) { a.m[i]-=b.m[i]; if(a.m[i]<0) a.m[i]+=10,a.m[i+1]--; } while(a.m[a.l]==0) a.l--; return a; } Mat operator * (Mat b) { Mat a=*this,c; for(int i=1;i<=a.l;i++) for(int j=1;j<=b.l;j++) { c.m[i+j-1]+=a.m[i]*b.m[j]; int k=c.m[i+j-1]/10; c.m[i+j-1]%=10; c.m[i+j]+=k; } c.l=a.l+b.l+5; while(c.m[c.l]==0) c.l--; return c; } Mat operator ^ (int b) { Mat a=*this,c; c.l=1,c.m[1]=1; for(;b;b>>=1,a=a*a) if(b&1) c=c*a; return c; } void print() { for(int i=l;i>=1;i--) printf("%d",m[i]);printf("\n"); }} f ,f1 ;int n,d;int main() { scanf("%d%d",&n,&d); if(d==0) {puts("1");return 0;} f.l=1,f.m[1]=1; for(int i=1;i<=d;i++) { f=f^n; f=f+1; if(i==d-1) f1=f; } f=f-f1; f.print(); return 0;}