10007  Count the Trees
Moderator: Board moderators

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
10007  Count the Trees
Hi
Is there a simple way of storing *VERY* big integers in C (around 10^50) ? Is <openssl/bn.h> allowed ? Or do we have to implement our own system ?
Thks
Julien
Is there a simple way of storing *VERY* big integers in C (around 10^50) ? Is <openssl/bn.h> allowed ? Or do we have to implement our own system ?
Thks
Julien
<openssl/bn.h> is not allowed.
simply use string and make ur own function
to reduce space and time u can mask the numbers to int or long int. suppose u r using an char type array to store a 18 digit number. so u need 18 bytes mem. but u can use 2 long int that takes 8 bytes mem to store the number.
hope u will develop the procedure to deal with big numbers!
simply use string and make ur own function
to reduce space and time u can mask the numbers to int or long int. suppose u r using an char type array to store a 18 digit number. so u need 18 bytes mem. but u can use 2 long int that takes 8 bytes mem to store the number.
hope u will develop the procedure to deal with big numbers!

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:

 Experienced poster
 Posts: 106
 Joined: Sun Feb 17, 2002 2:00 am
 Location: Seoul, South Korea
 Contact:
Use Java.Math.Biginteger
Java provide so simple solution. If you can use Java.Math.Biginteger
method, you'll handle biginteger easy.
Please check Java library reference. : )
method, you'll handle biginteger easy.
Please check Java library reference. : )
Base 100000000
Hi,
Does anyone know how to create a base 100000000 class? Am I need to use int array where every index hold 0  99999999 ('%' by 1000000000)? Is it very slow?
novice
Does anyone know how to create a base 100000000 class? Am I need to use int array where every index hold 0  99999999 ('%' by 1000000000)? Is it very slow?
novice

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Hi~~
You can convert the number to base 10000, which is capable of addition and multiplication without exceeding the boundary of int.
I have used this method to solve the problems which need the calculation of big numbers.
I have used this method to solve the problems which need the calculation of big numbers.
What's the problem with this one ??? i'm getting lots of segsegv....
#include<stdio.h>
#define NUM 33
#define MAX 15
long int facs[NUM][MAX];
long int cats[NUM][MAX];
long int finl[NUM][MAX];
void buildfacs();
void buildcats();
void buildfinl();
int main(void)
{
register int i;
int index;
buildfacs();
buildcats();
buildfinl();
while(1){
scanf("%d",&index);
if(index==0)
break;
for(i=MAX1;i>=0;i){
if(finl[index]!=0)
break;
}
printf("%ld",finl[index]);
for(i;i>=0;i)
printf("%04ld",finl[index]);
printf("\n");
}
return 0;
}
void buildfacs()
{
register int i,j;
for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
facs[j]=0;
}
facs[0][0]=1;
for(i=1;i<NUM;i++){
for(j=0;j<MAX;j++){
facs[j]+=(facs[i1][j]*i);
if(facs[j]>=10000){
facs[j+1]+=facs[j]/10000;
facs[j]%=10000;
}
}
}
}
void buildcats()
{
register int i,j,k,l;
for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
cats[j]=0;
}
cats[0][0]=1;
for(i=1;i<NUM;i++){
for(l=0;l<i;l++){
for(j=0;j<MAX;j++){
for(k=0;k<MAX;k++){
cats[i][j+k]+=(cats[l][j]*cats[i1l][k]);
if(cats[i][j+k]>=10000){
cats[i][j+k+1]+=cats[i][j+k]/10000;
cats[i][j+k]%=10000;
}
}
}
}
}
}
void buildfinl()
{
register int i,j,k;
for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
finl[i][j]=0;
}
for(i=1;i<NUM;i++){
for(j=0;j<MAX;j++){
for(k=0;k<MAX;k++){
finl[i][j+k]+=(facs[i][j]*cats[i][k]);
if(finl[i][j+k]>=10000){
finl[i][j+k+1]+=finl[i][j+k]/10000;
finl[i][j+k]%=10000;
}
}
}
}
}
[/c]
#include<stdio.h>
#define NUM 33
#define MAX 15
long int facs[NUM][MAX];
long int cats[NUM][MAX];
long int finl[NUM][MAX];
void buildfacs();
void buildcats();
void buildfinl();
int main(void)
{
register int i;
int index;
buildfacs();
buildcats();
buildfinl();
while(1){
scanf("%d",&index);
if(index==0)
break;
for(i=MAX1;i>=0;i){
if(finl[index]!=0)
break;
}
printf("%ld",finl[index]);
for(i;i>=0;i)
printf("%04ld",finl[index]);
printf("\n");
}
return 0;
}
void buildfacs()
{
register int i,j;
for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
facs[j]=0;
}
facs[0][0]=1;
for(i=1;i<NUM;i++){
for(j=0;j<MAX;j++){
facs[j]+=(facs[i1][j]*i);
if(facs[j]>=10000){
facs[j+1]+=facs[j]/10000;
facs[j]%=10000;
}
}
}
}
void buildcats()
{
register int i,j,k,l;
for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
cats[j]=0;
}
cats[0][0]=1;
for(i=1;i<NUM;i++){
for(l=0;l<i;l++){
for(j=0;j<MAX;j++){
for(k=0;k<MAX;k++){
cats[i][j+k]+=(cats[l][j]*cats[i1l][k]);
if(cats[i][j+k]>=10000){
cats[i][j+k+1]+=cats[i][j+k]/10000;
cats[i][j+k]%=10000;
}
}
}
}
}
}
void buildfinl()
{
register int i,j,k;
for(i=0;i<NUM;i++){
for(j=0;j<MAX;j++)
finl[i][j]=0;
}
for(i=1;i<NUM;i++){
for(j=0;j<MAX;j++){
for(k=0;k<MAX;k++){
finl[i][j+k]+=(facs[i][j]*cats[i][k]);
if(finl[i][j+k]>=10000){
finl[i][j+k+1]+=finl[i][j+k]/10000;
finl[i][j+k]%=10000;
}
}
}
}
}
[/c]
10007 WA after rejudged.
I originally solved this problem by using
following recursive formula:
f(0)=0;
f(1)=1;
f(n)=sigma(f(i)*f(ni)) 0<=i<n
and ans(n)=f(n)*n!
but after the limit of n had been changed, this method
is too slow and troublesome to code, could anyone
recommend a better one?
following recursive formula:
f(0)=0;
f(1)=1;
f(n)=sigma(f(i)*f(ni)) 0<=i<n
and ans(n)=f(n)*n!
but after the limit of n had been changed, this method
is too slow and troublesome to code, could anyone
recommend a better one?
Retired from SJTU Accelerator 2004

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
I did this problem a long time ago, and all I did was changed the array size, so correct me if I'm not too clear:
It is clear that Catalan numbers are used, with binary trees and all, and the lesser known way of writing Catalan numbers is:
2n! / (n! * (n+1)! )
If you don't understand above, look up on mathworld or google.
Then you realize there's n! way of labeling each of the tree, so you just multiply it by n!. I think the indices might be off by 1 in this explanation, and I think I just fudged it by fixing it until it matches the output.. but this was my general thought process.
It is clear that Catalan numbers are used, with binary trees and all, and the lesser known way of writing Catalan numbers is:
2n! / (n! * (n+1)! )
If you don't understand above, look up on mathworld or google.
Then you realize there's n! way of labeling each of the tree, so you just multiply it by n!. I think the indices might be off by 1 in this explanation, and I think I just fudged it by fixing it until it matches the output.. but this was my general thought process.