首页 > 代码库 > 【BZOJ】1089: [SCOI2003]严格n元树(递推+高精度/fft)

【BZOJ】1089: [SCOI2003]严格n元树(递推+高精度/fft)

http://www.lydsy.com/JudgeOnline/problem.php?id=1089

想了好久的递推式,,,然后放弃了QAQ

神思路!orz

首先我们设$f[i]$表示深度最大为i的n元树的数目,注意,是最大深度为i!

那么易得递推式

f[i]=f[i-1]^n+1

前面表示子树的情况乘积,后面表示树为1层!因为1层是合法的!即没有子女!

然后答案就是

f[d]-f[d-1]

!!!为什么要剪掉呢?因为看我们的转移,并不是深度为i,而是深度最大为i,那么为什么要这样减呢?理由很简单吧。。。f[d]表示深度最大为d的数目,f[d-1]表示深度最大为d-1的数目,那么我们只要深度为d,那么剪掉之。。。

然后还要特判!!!!我没特判wa了好久!!!!

当d=0的时候。。。。。。。。。。答案=1。。

然后蒟蒻我打了个fft做乘法。。。可是比普通乘法还慢?不明觉厉QAQ

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }const double PI=acos(-1.0);struct big {	static const int N=10005;	static const ll M=10000000;	ll a[N];	void clr() { memset(a, 0, sizeof(ll)*(a[0]+1)); a[0]=1; }	void upd() { int len=a[0]; while(len>1 && a[len]==0) --len; a[0]=len; }	big() { a[0]=1; memset(a, 0, sizeof a); }	big(ll k) { a[0]=1; memset(a, 0, sizeof a); *this=k; }	big(const big &k) { a[0]=1; memset(a, 0, sizeof a); *this=k; }	big(char *k) { a[0]=1; memset(a, 0, sizeof a); *this=k; }	big & operator=(ll x) {		clr(); int len=0;		if(x==0) len=1;		while(x) a[++len]=x%M, x/=M;		a[0]=len;		return *this;	}	big & operator=(char *s) {		clr();		int n=strlen(s), len=1; ll k=1;		for3(i, n-1, 0) {			a[len]+=k*(s[i]-‘0‘);			k*=10;			if(k>=M) { k=1; ++len; }		}		a[0]=len;		return *this;	}	big & operator=(const big &x) { clr(); memcpy(a, x.a, sizeof(ll)*(x.a[0]+1)); return *this; }	big & operator+(const big &x) {		static big t;		t.clr();		int len=max(x.a[0], a[0]), i=1; ll k=0;		for(; i<=len || k; ++i) {			t.a[i]=a[i]+x.a[i]+k;			k=t.a[i]/M;			if(t.a[i]>=M) t.a[i]%=M;		}		t.a[0]=i; t.upd();		return t;	}	big & operator-(const big &x) {		static big t;		t.clr();		for1(i, 1, a[0]) {			t.a[i]+=a[i]-x.a[i];			if(t.a[i]<0) --t.a[i+1], t.a[i]+=M;		}		t.a[0]=a[0]; t.upd();		return t;	}	big & operator*(const big &x) {		static big t;		t.clr();		fft(a+1, x.a+1, t.a+1, a[0], x.a[0], t.a[0]);		t.upd();		return t;	}	// big & operator*(const big &x) {	// 	static big t;	// 	t.clr();	// 	for1(i, 1, a[0]) for1(j, 1, x.a[0]) t.a[i+j-1]+=a[i]*x.a[j];	// 	int len=a[0]+x.a[0]-1, i=1; ll k=0;	// 	for(; i<=len || k; ++i) {	// 		t.a[i]+=k;	// 		k=t.a[i]/M;	// 		if(t.a[i]>=M) t.a[i]%=M;	// 	}	// 	t.a[0]=i; t.upd();	// 	return t;	// }	big & operator*(const ll &x) { static big t; t=x; t=(*this)*t; return t; }	big & operator+(const ll &x) { static big t; t=x; t=(*this)+t; return t; }	void P() {		printf("%lld", a[a[0]]);		for3(i, a[0]-1, 1) printf("%07lld", a[i]);	}	struct cp {		double r, i;		cp(double _r=0.0, double _i=0.0) : r(_r), i(_i) {}		cp operator + (const cp &x) { return cp(r+x.r, i+x.i); }		cp operator - (const cp &x) { return cp(r-x.r, i-x.i); }		cp operator * (const cp &x) { return cp(r*x.r-i*x.i, r*x.i+i*x.r); }	};	int rev[N];	void init(int &len) {		int k=1, t=0;		while(k<len) k<<=1, ++t;		len=k;		rep(i, len) {			k=t; int ret=0, x=i;			while(k--) ret<<=1, ret|=x&1, x>>=1;			rev[i]=ret;		}	}	void dft(cp *a, int n, int flag) {		static cp A[N];		rep(i, n) A[i]=a[rev[i]];		rep(i, n) a[i]=A[i];		int m, i, j, mid;		cp t, u;		for(m=2; m<=n; m<<=1) {			cp wn(cos(2.0*PI/m*flag), sin(2.0*PI/m*flag));			for(i=0; i<n; i+=m) {				cp w(1.0); mid=m>>1;				for(j=0; j<mid; ++j) {					u=a[i+j+mid]*w, t=a[i+j];					a[i+j]=t+u;					a[i+j+mid]=t-u;					w=w*wn;				}			}		}		if(flag==-1) rep(i, n) a[i].r/=n;	}	void fft(const ll *a, const ll *b, ll *c, const ll &la, const ll &lb, ll &lc) {		static cp x[N], y[N];		int len=la+lb-1;		init(len);		rep(i, len) x[i].r=a[i], x[i].i=0;		rep(i, len) y[i].r=b[i], y[i].i=0;		dft(x, len, 1); dft(y, len, 1);		rep(i, len) x[i]=x[i]*y[i];		dft(x, len, -1);		rep(i, len) c[i]=x[i].r+0.5;		rep(i, len) c[i+1]+=c[i]/M, c[i]%=M;		lc=len+1;	}};big f[35], k, r;int main() {	int n=getint(), d=getint();	if(!d) { puts("1"); return 0; }	f[0]=1;	for1(i, 1, d) {		r=1; k=f[i-1];		int t=n;		while(t) { if(t&1) r=r*k; t>>=1; k=k*k; }		f[i]=r+1;	}	r=f[d]-f[d-1];	r.P();	return 0;}

  

 


 

 

Description

如果一棵树的所有非叶节点都恰好有n个儿子,那么我们称它为严格n元树。如果该树中最底层的节点深度为d(根的深度为0),那么我们称它为一棵深度为d的严格n元树。例如,深度为2的严格2元树有三个,如下图:

给出n, d,编程数出深度为d的n元树数目。

Input

仅包含两个整数n, d( 0   <   n   <   =   32,   0  < =   d  < = 16)

Output

仅包含一个数,即深度为d的n元树的数目。

Sample Input

【样例输入1】
2 2

【样例输入2】
2 3

【样例输入3】
3 5

Sample Output

【样例输出1】
3

【样例输出2】
21

【样例输出2】
58871587162270592645034001

HINT

 

Source

 

 

【BZOJ】1089: [SCOI2003]严格n元树(递推+高精度/fft)