結果

問題 No.658 テトラナッチ数列 Hard
ユーザー beetbeet
提出日時 2018-03-02 22:29:59
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 1,554 bytes
コンパイル時間 2,826 ms
コンパイル使用メモリ 158,424 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-03 23:03:10
合計ジャッジ時間 4,278 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 54 ms
4,376 KB
testcase_05 AC 59 ms
4,380 KB
testcase_06 AC 70 ms
4,380 KB
testcase_07 AC 75 ms
4,376 KB
testcase_08 AC 87 ms
4,376 KB
testcase_09 AC 122 ms
4,380 KB
testcase_10 AC 122 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename T>
struct Kitamasa{
  using VT = vector<T>;
  VT a,c;
  vector<VT > rs;
  Int m,base;
  using F = function<T(T,T)>;
  F pl,ml;
  T d0,d1;
  
  Kitamasa(VT& A,VT &C,F pl,F ml,T d0,T d1)
    :a(A),c(C),rs(1),m(c.size()),base(1),pl(pl),ml(ml),d0(d0),d1(d1){
    a.insert(a.begin(),d0);
    rs[0].assign(2*m+1,d0);
    rs[0][1]=d1;
  }

  void form(VT &x){
    for(Int i=2*m;i>m;i--){
      for(Int j=1;j<m+1;j++)
	x[i-j]=pl(x[i-j],ml(c[m-j],x[i]));
      x[i]=d0;
    }
  }

  void add(VT x,VT y,VT &z){
    z.assign(2*m+1,d0);
    for(Int i=1;i<m+1;i++)
      for(Int j=1;j<m+1;j++)
	z[i+j]=pl(z[i+j],ml(x[i],y[j]));
    form(z);
  }
  
  void ensure_base(Int nbase){
    if(nbase<=base) return;
    rs.resize(nbase);
    for(Int i=base;i<nbase;i++)
      add(rs[i-1],rs[i-1],rs[i]);
    base=nbase;
  }

  T calc(long long n){
    n--;
    VT tmp,res(rs[0]);
    for(Int i=0;n;i++,n>>=1){
      ensure_base(i+1);
      if(~n&1) continue;
      swap(tmp,res);
      add(tmp,rs[i],res);
    }
    T ans=d0;
    for(Int i=1;i<m+1;i++) ans=pl(ans,ml(res[i],a[i]));
    return ans;
  }
  
};

//INSERT ABOVE HERE
signed main(){
  Int n=4;
  const Int MOD = 17;
  
  vector<Int> a(n,0),c(n,1);
  a[n-1]=1;
  Kitamasa<Int>::F pl=[](Int a,Int b){return (a+b)%MOD;};
  Kitamasa<Int>::F ml=[](Int a,Int b){return (a*b)%MOD;};
  Kitamasa<Int> fib(a,c,pl,ml,0,1);
  
  Int q;
  cin>>q;
  for(Int i=0;i<q;i++){
    Int p;
    cin>>p;
    cout<<fib.calc(p)<<endl;
  }
  return 0;
}
0