結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー a
提出日時 2015-04-27 00:03:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 39 ms / 5,000 ms
コード長 2,348 bytes
コンパイル時間 624 ms
コンパイル使用メモリ 52,092 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 03:10:14
合計ジャッジ時間 2,388 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |   scanf("%d%lld",&n,&k);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:58:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |     scanf("%d",&a[i]);
      |     ~~~~~^~~~~~~~~~~~

ソースコード

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