結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー aa
提出日時 2015-04-26 23:59:58
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,343 bytes
コンパイル時間 578 ms
コンパイル使用メモリ 53,692 KB
実行使用メモリ 813,916 KB
最終ジャッジ日時 2023-09-18 12:12:15
合計ジャッジ時間 2,857 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 2 ms
4,376 KB
testcase_21 MLE -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <deque>
#include <vector>

using namespace std;

const long long mod = 1e9+7;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
mat mul(mat&A,mat&B,ll M)
{
  mat C(A.size(),vec(B[0].size()));
  for(int i = 0; i < int(A.size()); i++) {
    for(int k = 0; k < int(B.size()); k++) {
      for(int j = 0; j < int(B[0].size()); j++) {
        C[i][j] = (C[i][j]+A[i][k]*B[k][j])%M;
      }
    }
  }
  return C;
}
mat pow(mat A,ll n,ll M)
{
  mat B(A.size(),vec(A.size()));
  for(int i = 0; i < int(A.size()); i++) {
    B[i][i] = 1;
  }
  while( n > 0 ) {
    if( n&1 ) B = mul(B,A,M);
    A = mul(A,A,M);
    n >>= 1;
  }
  return B;
}

long long s,t;
int n;
ll k;
deque<int> a;

long long pl(long long a,long long b) {
  return (a+b)%mod;
}

long long mi(long long a,long long b)
{
  return ((a-b)%mod+mod)%mod;
}

int main(void)
{
  scanf("%d%lld",&n,&k);
  mat p(n,vec(1));
  a.resize(n);
  s = t = 0;
  for( int i = 0; i < n; i++ ) {
    scanf("%d",&a[i]);
    p[n-i-1][0] = a[i];
    s = pl(s,a[i]);
  }
  t = s;
  --k;
  int res;
  a.push_back(s);
  if( n >= k ) {
    res = a[k];
    if( n == k ) t += a[k];
  } else if( k <= 1000000&&false ) {
    t += a.back();
    for( int i = 0; i < k-n; i++ ) {
      s = mi(s,a.front());
      s = pl(s,a.back());
      a.pop_front();
      a.push_back(s);
      t = pl(t,a.back());
    }
    res = a.back();
  } else {
    mat v(n,vec(n,0));
    for( int i = 0; i < n; i++ ) {
      v[0][n-i-1] = 1;
    }
    for( int i = 0; i < n-1; i++ ) {
      v[i+1][i] = 1;
    }
    {
      mat w = pow(v,k-n,mod);
      w = mul(w,p,mod);
      res = w[n-1][0];
    }
    {
      mat v(n+1,vec(n+1,0));
      for( int i = 0; i < n; i++ ) {
        v[0][n-i-1] = 1;
      }
      for( int i = 0; i < n; i++ ) {
        v[i+1][i] = 1;
      }
      v[n][n] = 1;
      mat p(n+1,vec(1,0));
      for( int i = 0; i < n; i++ ) {
        p[i][0] = a[n-i-1];
      }
      /*
      for( int i = 0; i < n+1; i++ ) {
        for( int j = 0; j < n+1; j++ ) {
          printf("%lld ",v[i][j]);
        }
        puts("");
      }
      */
      mat w = pow(v,k+1,mod);
      w = mul(w,p,mod);
      /*
      for( int i = 0; i < n+1; i++ ) {
        printf("%d:%lld\n",i,w[i][0]);
      }
      */
      t = w[n][0];
    }
  }
  printf("%d %lld\n",res,t);
  return 0;
}
0