BZOJ1089 [SCOI2003]严格n元树 【高精度+动态规划】

tonyfang posted @ 2015年8月30日 14:34 in BZOJ with tags c++ OI , 445 阅读

这题吧,就是个DP吧,加了个高精度。……

$s[i]$表示深度为1..d的严格n元树的数目,那么很明显,$s[i]=s[i-1]^{n}+1$,然后写个高精度就好了。

 

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int fg=10000;
struct bn{
	int len,a[310];
	void operator =	(int x) {a[1]=x;len=1;}
	int& operator [](int x) {return a[x];}
}s[20];
void operator ++(bn &b) {
	b[1]++;int g=1;
	while(b.a[g]==fg) b[g]=0,b[++g]++;
	if(g>b.len)b.len=g;
}
bn operator - (bn &a,bn &b) {
	bn c;memset(c.a,0,sizeof(c.a));
	for (int i=1;i<=a.len;++i) {
		c[i]+=a[i]-b[i];
		if(c[i]<0)c[i]+=fg,c[i+1]--;
		if(c[i])c.len=i;
	}return c;
}
void operator *=(bn &a,bn &b) {
	bn c;memset(c.a,0,sizeof(c.a));
	for(int i=1;i<=a.len;++i)for(int j=1;j<=b.len;++j) {
		c[i+j-1]+=a[i]*b[j];
		c[i+j]+=c[i+j-1]/fg;
		c[i+j-1]%=fg;
	}c.len=a.len+b.len;
	if(!c[c.len])c.len--;
	a=c;
}
void out(bn a) {
	printf("%d",a[a.len]);
	for (int i=a.len-1;i>=1;--i)printf("%04d",a[i]);
}
bn operator ^(bn a,int y) {
	bn c;c=1;
	while(y) {
		if(y&1)c*=a;
		a*=a;
		y>>=1;
	}return c;
}int n,d;int main() {
	scanf("%d%d",&n,&d);
	if(d==0) {printf("1\n");return 0;}
	s[0]=1;
	for(int i=1;i<=d;++i)s[i]=s[i-1]^n,++s[i];
	out(s[d]-s[d-1]);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter