首页 > 代码库 > BZOJ 1089 SCOI2003 严格n元树 动态规划+高精度
BZOJ 1089 SCOI2003 严格n元树 动态规划+高精度
题目大意:定义一棵深度为d的严格n元树为根的深度为0,最深的节点深度为d,且每一个非叶节点都有恰好n个子节点的树
给定n和d,求深度为d的严格n元树一共同拥有多少种
此题的递推部分并不难 首先我们设深度为i的严格n元树一共同拥有f[i]种 令S[i]为f[i]的前缀和
我们不难发现一棵深度为i下面的严格n元树由两部分组成:一个根节点,n棵子树。当中每棵子树的深度不超过i-1
每棵子树有S[i-1]种 一共n棵子树 于是S[i]=S[i-1]^n
嗯?是不是少了点东西?没错,另一种情况,这棵严格n元树本身就是一个根节点
于是S[i]=S[i-1]^n+1
然后看看例子。。
。妈蛋。
。。高精度。。。
事实上高精度不难写真的。。。
我的高精度就是一通操作符重载。。
。 连cout都重载了。。。。
顺便学到了非常多东西
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<iomanip> using namespace std; struct long_int{ int num[300],cnt; void operator = (int y) { num[1]=y; cnt=1; } int& operator [] (int x) { return num[x]; } }S[20]; void operator *= (long_int &x,long_int &y) { long_int z=S[19]; int i,j; for(i=1;i<=x.cnt;i++) for(j=1;j<=y.cnt;j++) { z[i+j-1]+=x[i]*y[j]; z[i+j]+=z[i+j-1]/10000; z[i+j-1]%=10000; } z.cnt=x.cnt+y.cnt; if(!z[z.cnt]) --z.cnt; x=z; } void operator ++ (long_int &x) { int i=1;x[1]++; while(x[i]==10000) x[i]=0,x[++i]++; } long_int operator - (long_int &x,long_int &y) { long_int z=S[19]; int i; for(i=1;i<=x.cnt;i++) { z[i]+=x[i]-y[i]; if(z[i]<0) z[i]+=10000,z[i+1]--; if(z[i]) z.cnt=i; } return z; } long_int operator ^ (long_int x,int y) { long_int z=S[19];z=1; while(y) { if(y&1) z*=x; x*=x; y>>=1; } return z; } ostream& operator << (ostream& os,long_int x) { int i; os<<x[x.cnt]; for(i=x.cnt-1;i;i--) os<<setfill(‘0‘)<<setw(4)<<x[i]; return os; } int n,d; int main() { int i; cin>>n>>d; if(!d) { puts("1"); return 0; } S[0]=1; for(i=1;i<=d;i++) S[i]=S[i-1]^n,++S[i]; cout<<S[d]-S[d-1]<<endl; }
BZOJ 1089 SCOI2003 严格n元树 动态规划+高精度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。