結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー aa
提出日時 2015-04-27 00:03:03
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 39 ms / 5,000 ms
コード長 2,348 bytes
コンパイル時間 584 ms
コンパイル使用メモリ 54,812 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-18 12:16:05
合計ジャッジ時間 3,443 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 39 ms
4,376 KB
testcase_03 AC 5 ms
4,376 KB
testcase_04 AC 15 ms
4,380 KB
testcase_05 AC 12 ms
4,376 KB
testcase_06 AC 15 ms
4,380 KB
testcase_07 AC 24 ms
4,380 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 19 ms
4,376 KB
testcase_10 AC 7 ms
4,376 KB
testcase_11 AC 8 ms
4,376 KB
testcase_12 AC 13 ms
4,376 KB
testcase_13 AC 6 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 30 ms
4,376 KB
testcase_16 AC 26 ms
4,376 KB
testcase_17 AC 8 ms
4,376 KB
testcase_18 AC 27 ms
4,380 KB
testcase_19 AC 37 ms
4,380 KB
testcase_20 AC 16 ms
4,380 KB
testcase_21 AC 17 ms
4,376 KB
testcase_22 AC 16 ms
4,376 KB
testcase_23 AC 3 ms
4,380 KB
testcase_24 AC 9 ms
4,380 KB
testcase_25 AC 8 ms
4,376 KB
testcase_26 AC 9 ms
4,380 KB
testcase_27 AC 9 ms
4,376 KB
testcase_28 AC 4 ms
4,376 KB
testcase_29 AC 16 ms
4,376 KB
testcase_30 AC 36 ms
4,380 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 11 ms
4,376 KB
testcase_33 AC 17 ms
4,376 KB
testcase_34 AC 14 ms
4,376 KB
testcase_35 AC 11 ms
4,380 KB
testcase_36 AC 28 ms
4,376 KB
testcase_37 AC 3 ms
4,376 KB
testcase_38 AC 33 ms
4,376 KB
testcase_39 AC 13 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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 ) {
    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,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