BZOJ1089/SCOI2003/严格n元树

Posted on By 二价氢

显然的,这题有递推公式

临界值为

我们来想一下

如果所有的子结点都挂了子树,那么这子树的层树最深为层,由此可以递归下去,状态转移了

如果所有的子结点都每挂子树,那么总共有1种方式(就是都不挂)

最后的结果要减去层树小于等于层的树的个数

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;
}