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();
}

Download