显然的,这题有递推公式
\[f_i=f_{i-1}^n+1\]临界值为\(f_0=1\)
我们来想一下
如果所有的子结点都挂了子树,那么这子树的层树最深为\(n-1\)层,由此可以递归下去,状态转移了
如果所有的子结点都每挂子树,那么总共有1种方式(就是都不挂)
最后的结果要减去层树小于等于\(d\)层的树的个数
AC-Code(Python)
import sys;
lastnum=0;
thisnum=1;
n,d=map(int,sys.stdin.readline().split());
for i in range (1,d+1):
lastnum=thisnum;
thisnum=lastnum**n+1;
print(thisnum-lastnum)
AC-Code(C++)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct INT{
int a[100];
}lastnum,thisnum;
INT operator * (INT a,INT b)
{
INT ret=null;
for (int i=0;i<100;i++)
ret.a[i]=0;
for (int i=0;i<50;i++)
{
for (int j=0;j<50;j++)
{
ret.a[i+j]+=a.a[i]*b.a[j];
}
}
for (int i=0;i<99;i++)
{
ret.a[i+1]+=ret.a[i]/10000;
ret.a[i]%=10000;
}
return ret;
}
INT POW(INT a,int b)
{
if (b==1)
return a;
if (b%2)
{
INT ret=POW(a,b-1);
return ret*a;
}else
{
INT ret=POW(a,b/2);
return ret*ret;
}
}
INT operator + (INT a,int b)
{
a.a[0]+=b;
for (int i=0;i<99;i++)
{
if (a.a[i]>=10000)
{
a.a[i+1]+=1;
a.a[i]-=10000;
}
}
return a;
}
INT operator - (INT a,INT b)
{
for (int i=0;i<99;i++)
{
a.a[i]-=b.a[i];
if (a.a[i]<0)
{
a.a[i+1]-=1;
a.a[i]+=10000;
}
}
return a;
}
int main()
{
int n,d;
memset(&thisnum,0,sizeof(thisnum));
memset(&lastnum,0,sizeof(lastnum));
thisnum.a[0]=1;
scanf("%d%d",&n,&d);
for (int i=1;i<=d;i++)
{
lastnum=thisnum;
thisnum=POW(lastnum,n)+1;
}
thisnum=thisnum-lastnum;
int w=98;
while (w&&!thisnum.a[w]) w--;
printf("%d",thisnum.a[w]);
for (int i=w-1;i>=0;i--)
printf("%04d",thisnum.a[i]);
printf("\n");
return 0;
}