hdu 1134 卡特兰数(大数模板)
发布时间:2020-12-14 03:14:37 所属栏目:大数据 来源:网络整理
导读:卡特兰数 递推公式:?C(n)=C(2n,n)/(n+1) ?即用数组表示为 c[i]=c[i-1]*(4*i-2)/(i+1); 一般形式 直接 表达 c[1]=1; for(i=2;i40;i++) { c[i]=c[i-1]*(4*i-2)/(i+1); } ?一般 不超过33 ?超过33 后 数组溢出, 或者 ? 超过44 后溢出 dp[1][1]=1; // 可到40for(i
卡特兰数 递推公式:?C(n)=C(2n,n)/(n+1) ?即用数组表示为c[i]=c[i-1]*(4*i-2)/(i+1); 一般形式 直接 表达
c[1]=1; for(i=2;i<40;i++) { c[i]=c[i-1]*(4*i-2)/(i+1); } ?一般 不超过33 ?超过33 后 数组溢出, 或者 ? 超过44 后溢出
dp[1][1]=1; // 可到40 for(i=2;i<40;i++) for(j=1;j<=i;j++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } dp[i][i]==// 卡特兰数 因此 当 要求44-100 内时 就要用到大数模板,来进行运算 针对这个题,可以现 做预处理 ? 引用c[i]=c[i-1]*(4*i-2)/(i+1);的思想,?用大数据来算
#include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> /* 先 打表,卡特兰数,大数模板 */ using namespace std; const int MAXN=10000; const int DEL=4; const int N=100; int a[102][N+2]; void multiply(int a[],int b)//乘法 { int i,temp=0; for(i=N-1;i>=0;i--) { temp+=a[i]*b; a[i]=temp%MAXN; temp/=MAXN; } } void divid(int a[],int b)//除法 { int temp=0,i; for(i=0;i<N;i++) { temp=temp*MAXN+a[i]; a[i]=temp/b; temp=temp%b; } } int main() { int i,n; memset(a[1],sizeof(a[1])); a[1][N-1]=1; for(i=2;i<N+1;i++)//打表 { memcpy(a[i],a[i-1],N*sizeof(int)); multiply(a[i],4*i-2);//乘法 divid(a[i],i+1);//除法 } while(~scanf("%d",&n)&&n!=-1) { for(i=0;i<N&a[n][i]==0;i++);// 去掉前面的0 printf("%d",a[n][i]); for(i=i+1;i<N;i++) { printf("%04d",a[n][i]);// 无0 补0 } printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |