杭电1023 Train problemII(卡塔兰大数)
发布时间:2020-12-14 03:00:44 所属栏目:大数据 来源:网络整理
导读:Train Problem II Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5923????Accepted Submission(s): 3219 Problem Description As we all know the Train Problem I,the boss of the Ignatius
Train Problem IITime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5923????Accepted Submission(s): 3219
Problem Description
As we all know the Train Problem I,the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order,how many orders that all the trains can get out of the railway.
?
Input
The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.
?
Output
For each test case,you should output how many ways that all the trains can get out of the railway.
?
Sample Input
?
Sample Output
?
Author
Ignatius.L
/* Time:2014-11-28 20:30 更新 */ //卡特兰大数 //f[n]=f[n-1]*(4*n-2)/(n+1) 1,2,5,14 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAX=1000; int f[105][MAX]; int digit[MAX]; void Catalan(){ memset(f,sizeof(f)); f[0][0]=1;f[1][0]=1; digit[0]=digit[1]=0; int i,j,t; for(i=2;i<=100;i++){ int t=0;digit[i]=digit[i-1]; for(j=0;j<=digit[i];j++){ f[i][j]=f[i-1][j]*(4*i-2)+t; t=f[i][j]/10; f[i][j]%=10; if(t&&j+2>=digit[i]){ digit[i]++; } }/* for(j=digit[i];j>=0;j--){ printf("%d",f[i][j]); }puts("");*/ t=0; for(j=digit[i];j>=0;j--){ f[i][j]=f[i][j]+t*10; t=f[i][j]%(i+1); f[i][j]/=(i+1); } while(f[i][digit[i]]==0)digit[i]--; } } int main(){ int i,n; Catalan(); while(scanf("%d",&n)!=EOF){ for(i=digit[n];i>=0;i--){ printf("%d",f[n][i]); }puts(""); //printf("%dn",digit[n]); } return 0; } /* 被大数吓怕了,卡特兰大数,因为是大数与小数的运算,所以也不是很难,看见包子早就做了,我也做过,不过64位也wa知道是大数就不敢碰了 加油!!! Time:2014-10-3 17:54 */ #include<cstdio>//卡特兰数公式f[n]=f[n-1]*(4n-2)/(n+1) #include<cstring> #define MAX 220 int a[MAX][MAX],b[MAX];//b数组来记录每个数的位数 void Init(){ a[1][0]=1;b[1]=0; int i,k=1;//k表示位数 int z; for(i=2;i<102;i++){ for(j=0;j<k;j++) a[i][j]=a[i-1][j]*(4*i-2); z=0; for(j=0;j<k;j++){ a[i][j]+=z; z=a[i][j]/10; a[i][j]%=10; } while(z){ a[i][k++]=z%10; z/=10; } z=0; for(j=k-1;j>=0;j--){ a[i][j]=a[i][j]+z*10; z=a[i][j]%(i+1); a[i][j]/=(i+1); } while(a[i][k-1]==0)k--;//注意:是a[][k-1] 不是k b[i]=k-1; } } int main(){ int N; Init(); while(scanf("%d",&N)!=EOF){ for(int i=b[N];i>=0;i--) printf("%d",a[N][i]); puts(""); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |