TREEPATH - Đường đi trên cây
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <iostream>
//#include <conio.h>
#define base 100000000
using namespace std;
struct solon
{
int so;
long long a[500];
solon(){}
solon(long long x){
so = 1;
a[1] = x;
}
};
solon tong (solon A,solon B)
{
int du = 0;
solon C;
if(A.so<B.so)
{
C = A;
A = B;
B = C;
}
for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0;
C.so = A.so;
for(int i = 1;i<=A.so;i++)
{
C.a[i] = (A.a[i]+B.a[i]+du)%base;
du = (A.a[i]+B.a[i]+du)/base;
}
if(du>0) {C.so++; C.a[C.so] = du;}
return C;
}
solon tichnho(solon A,long long k,int chuso)
{
solon C;
long long du = 0;
C.so = A.so+chuso;
for(int i = 1;i<=chuso;i++)
C.a[i] = 0;
for(int i = chuso+1;i<=chuso+A.so;i++)
{
C.a[i] = (A.a[i-chuso]*k+du)%base;
du = (A.a[i-chuso]*k+du)/base;
}
if(du>0) {C.so++; C.a[C.so] = du;}
return C;
}
solon tich(solon A,solon B)
{
solon C;
C.so = 1; C.a[1] = 0;
for(int i = 1;i<=B.so;i++)
{
C = tong(C,tichnho(A,B.a[i],i-1));
}
return C;
}
void print(solon A)
{
printf("%lld",A.a[A.so]);
for(int i = A.so-1;i>=1;i--)
printf("%08lld",A.a[i]);
}
solon KQ,run,T,cong,the,nhanh;
char s[2222];
int main()
{
scanf("%s",s);
KQ = solon(1);
run = solon(1);
nhanh = solon(1);
for(int i = 0;i<strlen(s);i++){
if(s[i]=='L'){
run = tichnho(run,3,0);
KQ = tong(KQ,run);
}
else if(s[i]=='C'){
run = tong(tichnho(run,3,0),nhanh);
KQ = tong(KQ,run);
}
else if(s[i]=='R'){
run = tong(tichnho(run,3,0),tichnho(nhanh,2,0));
KQ = tong(KQ,run);
}
else if(s[i]=='*'){
the = run;
run = tong(tichnho(run,9,0),tichnho(nhanh,3,0));
KQ = tong(tichnho(KQ,4,0),run);
run = tong(run,the);
nhanh = tichnho(nhanh,4,0);
}
//print(KQ);
//printf("\n");
}
print(KQ);
//getch();
}