高精度/递推
Orz Hzwer……
然而我想多了……
理解以后感觉黄学长的递推好精妙啊
顺便学到了一份高精度的板子= =233
引用下题解：
/**************************************************************
Problem: 1089
User: Tunix
Language: C++
Result: Accepted
Time:0 ms
Memory:1352 kb
****************************************************************/ //BZOJ 1089
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/
struct bint{
int l,v[];
bint(){l=;memset(v,,sizeof v);}
int& operator [] (int x){return v[x];}
}f[];
const int Limit=;
void print(bint a){
printf("%d",a[a.l]);
D(i,a.l-,) printf("%04d",a[i]);
puts("");
}
bint operator * (bint a,bint b){
bint c;
F(i,,a.l+b.l) c[i]=;
F(i,,a.l) F(j,,b.l)
c[i+j-]+=a[i]*b[j];
c.l=a.l+b.l;
F(i,,c.l)
if (c[i]>=Limit){
if (i==c.l){
c.l++;
c[i+]=c[i]/Limit;
}else c[i+]+=c[i]/Limit;
c[i]%=Limit;
}
while(c.l> && !c[c.l]) c.l--;
return c;
}
bint operator + (bint a,int p){
a[]+=p;
int now=;
while(a[now]>=Limit){
a[now+]+=a[now]/Limit;
a[now]%=Limit;
now++;
a.l=max(a.l,now);
}
return a;
}
bint operator - (bint a,bint b){
F(i,,a.l){
a[i]-=b[i];
if (a[i]<){
a[i]+=Limit;
a[i+]--;
}
}
while(a.l> && !a[a.l]) a.l--;
return a;
}
bint operator ^ (bint a,int b){
bint r; r[r.l=]=;
for(;b;b>>=,a=a*a)
if (b&) r=r*a;
return r;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1089.in","r",stdin);
freopen("1089.out","w",stdout);
#endif
int n=getint(),d=getint();
f[][f[].l=]=;
F(i,,d) f[i]=(f[i-]^n)+;
print(f[d]-f[d-]);
return ;
}
1089: [SCOI2003]严格n元树
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 977 Solved: 500
[Submit][Status][Discuss]
Description
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：
给出n, d，编程数出深度为d的n元树数目。
Input
仅包含两个整数n, d( 0 < n < = 32, 0 < = d < = 16)
Output
仅包含一个数，即深度为d的n元树的数目。
Sample Input
【样例输入1】
2 2
2 2
【样例输入2】
2 3
【样例输入3】
3 5
Sample Output
【样例输出1】
3
3
【样例输出2】
21
【样例输出2】
58871587162270592645034001