Typical DP Contest T問題 - フィボナッチ

Source

Typical DP Contest
問題文

問題概要

$K+1$ 項間の漸化式
$\quad A_1 = A_2 = \cdots = A_K$
$\quad A_i = A_{i-1} + A_{i-2} + \cdots + A_{i-K}$（$i > K$）
で定義される数列の第 $N$ 項 $A_N$ を ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．

解法

$K+1$ 項間の線形の漸化式は $O(K^2 \log N)$ で計算できる．
行列べき乗に帰着すると，行列がコンパニオン行列になるので，その形に着目すれば良い．
または，$x^K = x^{K-1} + x^{K-2} + \cdots + x^0$ という条件のもとで，$x^N$ を求め $x^i$ を $A_i$ に置き換えれば良い（$i < K$）．
この多項式は繰り返し二乗法を行えば $O(K^2 \log N)$ で計算できる．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

void Kitamasa_mul(ll A[], ll c[], int d, ll md, ll limit, void *mem){int i,j;ll *C=(ll*)mem;rep(i,2*d-1)C[i]=0;rep(i,d)rep(j,d){C[i+j]+=A[i]*A[j];if(C[i+j]>=limit||C[i+j]<=-limit)C[i+j]%=md;}for(i=2*d-2;i>=d;i--){if(C[i]>=md||C[i]<=-md)C[i]%=md;rep(j,d){C[i-d+j]+=C[i]*c[j];if(C[i-d+j]>=limit||C[i-d+j]<=-limit)C[i-d+j]%=md;}}rep(i,d){A[i]=C[i];if(A[i]>=md||A[i]<=-md)A[i]%=md;}}
void Kitamasa_add(ll A[], ll c[], int d, ll md){int i;ll C;C=A[d-1];for(i=d-1;i;i--)A[i]=A[i-1];A[0]=0;rep(i,d){A[i]+=c[i]*C;if(A[i]<-md||A[i]>=md)A[i]%=md;}}
ll Kitamasa(ll n, ll a[], ll c[], int d, ll md, void *mem){int i,z=0;ll s,*A,*r,limit=((1ULL<<63)-1)-(ull)(md-1)*(md-1);r=(ll*)mem;for(;;){r[z++]=n;if(n<d)break;n/=2;}A=r+z;mem=(void*)(A+d);rep(i,d)A[i]=0;A[r[--z]]=1;while(z--){Kitamasa_mul(A,c,d,md,limit,mem);if(r[z]!=r[z+1]*2)Kitamasa_add(A,c,d,md);}s=0;rep(i,d){s+=a[i]*A[i];if(s>=limit||s<=-limit)s%=md;}if(s<=-md||s>=md)s%=md;return s;}

int main(){
  int i, j;
  int K, N;
  ll a[2000], c[2000];
  int res;
  void *mem = malloc(10000000);

  reader(&K,&N); N--;
  rep(i,K) a[i] = c[i] = 1;
  res = Kitamasa(N, a, c, K, 1000000007, mem);
  if(res < 0) res += 1000000007;
  writer((int)res,'\n');

  return 0;
}

Current time: 2024年04月19日13時30分26秒
Last modified: 2014年11月07日20時55分15秒 (by laycrs)
Tags: Competitive_Programming AtCoder Typical_DP_Contest
トップページに戻る

Logged in as: unknown user (not login)

ログイン：