1089: [SCOI2003]严格n元树
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 762 Solved: 387
[Submit][Status]
Description
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：
![BZOJ1089: [SCOI2003]严格n元树](https://image.shishitao.com:8440/aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhBdmQzZDNMbXg1WkhONUxtTnZiUzlLZFdSblpVOXViR2x1WlM5cGJXRm5aWE12TVRBNE9TOHhMbXB3Wnc9PS5qcGc%3D.jpg?w=700&webp=1 "BZOJ1089: [SCOI2003]严格n元树")
给出n, d，编程数出深度为d的n元树数目。
Input
仅包含两个整数n, d( 0 < n < = 32, 0 < = d < = 16)
Output
仅包含一个数，即深度为d的n元树的数目。
Sample Input
2 2
【样例输入2】
2 3
【样例输入3】
3 5
Sample Output
3
【样例输出2】
21
【样例输出2】
58871587162270592645034001
HINT
Source
题解：
先说一下此题我的想法（尽管没有A掉。。。）
考虑递推解此题：
设f[i]表示深度为i的严格n元树的数目，g[i]表示深度为（1--i）的严格n元树的数目。
则我们有如下递推式：
1.f[i]=g[i-1]^n-g[i-2]^n
2.g[i]=g[i-1]+f[i]
第二个是显然的，我们来说一下第一个是怎么来的。
因为我们从i-1递推到i，所以考率在n棵子树上加一个根节点，其余为原先的子树
因为要保证这棵树的深度达到n，所以至少有一个子树的深度达到n-1，
所以每个子树可以有g[i-1]种形态，n棵就是g[i-1]^n，然后去掉不合法的，
不合法的就是每个子树的深度都在1--i-2，即有g[i-2]种选择，也就是 g[i-2]^n
然后如果我们使用累加法的话可以发现 g[i]=g[i-1]^n+1，貌似很简单了？
TLE！！！尽管没有试，但我想是这样的，因为这个复杂度的话，ans必须<=4000位，看起来貌似不可能那么少。。。
高精度乘高精度太浪费时间了，我暂时没有想到好的解决办法。
贴一下上面的代码（没有用累加法）
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 50
#define maxm 500000
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 10000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,f[maxn][maxm],g[][maxm],t[maxm],c[maxm];
inline void writeln(int *a)
{
cout<<a[a[]];
for3(i,a[]-,)cout<<a[i];cout<<endl;
}
inline void update(int *a)
{
for1(i,a[])
{
a[i+]+=a[i]/mod;
a[i]%=mod;
if(a[a[]+])a[]++;
}
}
inline void mul(int *a,int x)
{
for1(i,a[])a[i]*=x;
update(a);
}
inline void jia(int *a,int *b)
{
a[]=max(a[],b[]);
for1(i,a[])
{
a[i]+=b[i];
a[i+]+=a[i]/mod;
a[i]%=mod;
}
while(!a[a[]])a[]--;
}
inline void cheng(int *a,int *b)
{
memset(c,,sizeof(c));
for1(i,a[])
for1(j,b[])
{
c[i+j-]+=a[i]*b[j];
c[i+j]+=c[i+j-]/mod;
c[i+j-]%=mod;
}
c[]=a[]+b[]+;
while(!c[c[]]&&c[])c[]--;
memcpy(a,c,sizeof(c));
}
inline void jian(int *a,int *b)
{
for1(i,a[])
{
a[i]-=b[i];
if(a[i]<)a[i]+=mod,a[i+]-=;
}
while(!a[a[]])a[]--;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();
f[][f[][]=]=;
g[][g[][]=]=;
g[][g[][]=]=;
for2(i,,m)
{
f[i][f[i][]=]=;
for1(j,n)cheng(f[i],g[]);
t[t[]=]=;
for1(j,n)cheng(t,g[]);
jian(f[i],t);
jia(g[],f[i-]);
jia(g[],f[i]);
}
printf("%d",f[m][f[m][]]);
for3(i,f[m][]-,)printf("%04d",f[m][i]);
return ;
}
感觉不会再爱了，这居然就是正解QAQ
不会貌似别人解释的更简单，直接推g[i]的表达式也很简单。
妈蛋，数据范围给的太大了，和lydsy要过来数据发现全是非常小的T_T
我做了2天多，一直在对拍自己的程序为什么出错，AC的程序运行过程中答案为什么会越来越小，我的程序为什么10 15的点都跑不出来，而且位数剧增
今天才发现是别人的空间爆了啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
还以为是我的程序错了啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
看来我的推断没有错，如果数据范围真如题中所说，那么答案的位数就太大了。
我要去建议lydsy修改此题的题面，不要再像坑我一样坑了其他人。。。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 500+100
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 10000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
class bigg
{
public:
int num[maxn], len;
bigg()
{
memset(num,,sizeof(num));
len=;
}
bigg operator = (const bigg &b)
{
memset(num,,sizeof(num));
len=b.len;
for1(i,len)num[i]=b.num[i];
return(*this);
}
bigg operator = (int b)
{
memset(num,,sizeof());
if (b==)
{
len=;
return(*this);
}
len=;
while(b>)
{
num[++len]=b%mod;
b/=mod;
}
return (*this);
}
bigg operator * (const bigg &b)
{
bigg ans;
ans=;
if (len==&&num[]==||b.len==&&b.num[]==)
return ans;
ans.len=len+b.len-;
for1(i,len)
for1(j,b.len)
{
ans.num[i+j-]+=num[i]*b.num[j];
ans.num[i+j]+=ans.num[i+j-]/mod;
ans.num[i+j-]%=mod;
}
if (ans.num[ans.len+])ans.len++;
while(!ans.num[ans.len])ans.len--;
return ans;
}
bigg operator - (const bigg &b)
{
bigg ans;
ans=;
ans.len=len;
for1(i,len)
{
ans.num[i]+=num[i]-b.num[i];
if (ans.num[i]<)
{
ans.num[i+]--;
ans.num[i]+=mod;
}
}
while (ans.len>&&!ans.num[ans.len]) ans.len--;
return ans;
}
bigg operator + (const bigg &b)
{
bigg ans;
ans=;
ans.len=max(len,b.len);
for1(i,ans.len)
{
ans.num[i]+=num[i]+b.num[i];
ans.num[i+]=ans.num[i]/mod;
ans.num[i]%=mod;
}
if (ans.num[ans.len+])ans.len++;
return ans;
}
void print()
{
printf("%d",num[len]);
for3(i,len-,)printf("%04d",num[i]);
printf("\n");
}
}; int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n, deep;
scanf("%d%d", &n, &deep);
if (deep == )
{
printf("1\n");
return ;
}
bigg fpre, fnow, f1;
fpre=,f1=;
for1(i,deep)
{
fnow=;
for1(j,n)fnow=fnow*fpre;
fnow=fnow+f1;
if (i!= deep) fpre=fnow;
}
fnow=fnow-fpre;
fnow.print();
return ;
}
不过还是有几点收获的：
1.捞到一个高精度模版
2.class里数组要开小