BZOJ 1089 SCOI2003 严格n元树 动态规划+高精度

题目大意：定义一棵深度为d的严格n元树为根的深度为0，最深的节点深度为d，且每一个非叶节点都有恰好n个子节点的树

给定n和d，求深度为d的严格n元树一共同拥有多少种

此题的递推部分并不难 首先我们设深度为i的严格n元树一共同拥有f[i]种 令S[i]为f[i]的前缀和

我们不难发现一棵深度为i下面的严格n元树由两部分组成：一个根节点，n棵子树。当中每棵子树的深度不超过i-1

每棵子树有S[i-1]种 一共n棵子树 于是S[i]=S[i-1]^n

嗯？是不是少了点东西？没错，另一种情况，这棵严格n元树本身就是一个根节点

于是S[i]=S[i-1]^n+1

然后看看例子。。

。妈蛋。

。。高精度。。。

事实上高精度不难写真的。。。

我的高精度就是一通操作符重载。。

。 连cout都重载了。。。。

顺便学到了非常多东西

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<iomanip>

using namespace std;

struct long_int{

	int num[300],cnt;

	void operator = (int y)

	{

		num[1]=y;

		cnt=1;

	}

	int& operator [] (int x)

	{

		return num[x];

	}

}S[20];

void operator *= (long_int &x,long_int &y)

{

	long_int z=S[19];

	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[19];

	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[19];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];

	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;

}