NKTOSS - Tung đồng xu
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <iostream>
//#include <conio.h>
#define base 1000000000
using namespace std;
struct solon
{
int so;
long long a[400];
};
int n,k;
solon F[11111],t;
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 tich2(solon A){
solon C;
int du = 0;
C.so = A.so;
for(int i = 1;i<=A.so;i++){
C.a[i] = (A.a[i]*2+du);
if(C.a[i]>=base){
C.a[i]-=base;
du = 1;
}
else du = 0;
}
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("%09lld",A.a[i]);
}
solon hieu(solon A,solon B){
solon C; C.so = A.so;
for(int i = B.so+1;i<=A.so;i++)
B.a[i] = 0;
int du = 0;
for(int i = 1;i<=A.so;i++){
C.a[i] = A.a[i]-B.a[i]-du;
if(C.a[i]<0){
C.a[i]+=base;
du = 1;
}
else du = 0;
}
while(C.a[C.so]==0) C.so--;
if(C.so==0) C.so = 1;
return C;
}
solon Hieu(solon A,solon B){
solon C; C.so = A.so;
int du = 0;
for(int i = 1;i<=A.so;i++){
if(i>B.so) B.a[i] = 0;
if(i>t.so) t.a[i] = 0;
C.a[i] = A.a[i]-B.a[i]+t.a[i]-du;
if(C.a[i]<0){
C.a[i]+=base;
du = 1;
}
else if(C.a[i]>=base){
C.a[i]-=base;
du = -1;
}
else du = 0;
}
if(du == -1) C.a[++C.so] = 1;
while(C.a[C.so]==0) C.so--;
if(C.so==0) C.so = 1;
return C;
}
int main()
{
scanf("%d %d",&n,&k);
t.so = 1; t.a[1] = 1;
for(int i = 0;i<=n;i++){
if(i<k){
F[i].so = 1 ;
F[i].a[1] = 0;
}
else if(i==k) {
F[i].so = 1;
F[i].a[1] = 1;
}
else{
F[i] = Hieu(tich2(F[i-1]),F[i-k-1]);
t = tich2(t);
}
}
print(F[n]);
// getch();
}