bzoj 1089: [SCOI2003]严格n元树【dp+高精】

设f[i]为深度为i的n元树数目，s为f的前缀和

s[i]=s[i-1]^n+1，就是增加一个根，然后在下面挂n个子树，每个子树都有s[i-1]种

写个高精就行了，好久没写WA了好几次……

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=55,mod=1e8;

int n,m;

struct qwe

{

	long long a[N];

	void clr()

	{

		memset(a,0,sizeof(a));

	}

	qwe operator + (const qwe &b) const

	{

		qwe c;

		c.clr();

		for(int i=1;i<=50;i++)

		{

			c.a[i]+=a[i]+b.a[i];

			c.a[i+1]+=c.a[i]/mod;

			c.a[i]%=mod;

		}

		return c;

	}

	qwe operator -(const qwe &b) const

	{

		qwe c;

		c.clr();

		for(int i=1;i<=50;i++)

		{

			c.a[i]+=a[i]-b.a[i];

			if(c.a[i]<0)

			{

				c.a[i]+=mod;

				c.a[i+1]--;

			}

		}

		return c;

	}

	qwe operator * (const qwe &b) const

	{

		qwe c;

		c.clr();

		for(int i=1;i<=50;i++)

			for(int j=1;j+i-1<=50;j++)

				c.a[j+i-1]+=a[i]*b.a[j];

		for(int i=1;i<=50;i++)

		{

			c.a[i+1]+=c.a[i]/mod;

			c.a[i]%=mod;

		}

		return c;

	}

}s[N],y;

qwe ksm(qwe a,int b)

{

	qwe r=y;

	while(b)

	{

		if(b&1)

			r=r*a;

		a=a*a;

		b>>=1;

	}

	return r;

}

int main()

{

	scanf("%d%d",&n,&m);

	if(m==0)

	{

		puts("1");

		return 0;

	}

	y.a[1]=1;

	s[0]=y;

	for(int i=1;i<=m;i++)

		s[i]=ksm(s[i-1],n)+y;

	qwe ans=s[m]-s[m-1];

	int l=50;

	while(!ans.a[l])

		l--;

	printf("%lld",ans.a[l]);

	for(int i=l-1;i>=1;i--)

		printf("%08lld",ans.a[i]);

	return 0;

}

巴特西

bzoj 1089: [SCOI2003]严格n元树【dp+高精】

最新文章

热门文章