首页 > 代码库 > 【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
2 2
【样例输入2】
2 3
【样例输入3】
3 5
Sample Output
【样例输出1】
3
【样例输出2】
21
【样例输出2】
58871587162270592645034001
3
【样例输出2】
21
【样例输出2】
58871587162270592645034001
HINT
Source
【BZOJ】1089: [SCOI2003]严格n元树(递推+高精度/fft)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。