#432273 (C++17) No.658 テトラナッチ数列 Hard

• 問題: No.658 テトラナッチ数列 Hard
• ユーザー: beet
• 提出日時: 2020-02-21 17:16:40
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 41 ms / 2,000 ms
• コード長: 4,769 bytes
• コンパイル時間: 2,349 ms
• コンパイル使用メモリ: 202,552 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-17 06:47:22
• 合計ジャッジ時間: 2,947 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	16 ms; 5,376 KB
testcase_05	AC	18 ms; 5,376 KB
testcase_06	AC	22 ms; 5,376 KB
testcase_07	AC	24 ms; 5,376 KB
testcase_08	AC	28 ms; 5,376 KB
testcase_09	AC	41 ms; 5,376 KB
testcase_10	AC	40 ms; 5,376 KB

ソースコード

#define PROBLEM "https://yukicoder.me/problems/1973"

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

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}
//END CUT HERE
#ifndef call_from_test

//INSERT ABOVE HERE
signed ABC127_E(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int h,w,k;
  cin>>h>>w>>k;
  using M = Mint<int>;

  M ans{0};
  for(int d=1;d<h;d++)
    ans+=M(d)*M(h-d)*M(w)*M(w);

  for(int d=1;d<w;d++)
    ans+=M(d)*M(w-d)*M(h)*M(h);

  ans*=M::comb(h*w-2,k-2);
  cout<<ans<<endl;
  return 0;
}
/*
  verified on 2019/06/12
  https://atcoder.jp/contests/abc127/tasks/abc127_e
*/

signed main(){
  //ABC127_E();
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename R>
struct Kitamasa{
  using VR = vector<R>;
  VR cs;
  vector<VR> rs;
  int m;

  Kitamasa(const VR &C)
    :cs(C),rs(1),m(C.size()){
    rs[0].assign(2*m+1,R::add_identity());
    rs[0][1]=R::mul_identity();
  }

  VR merge(const VR &xs,const VR &ys){
    VR zs(2*m+1,R::add_identity());
    for(int i=1;i<=m;i++)
      for(int j=1;j<=m;j++)
        zs[i+j]=zs[i+j]+(xs[i]*ys[j]);

    for(int i=2*m;i>m;zs[i--]=R::add_identity())
      for(int j=1;j<=m;j++)
        zs[i-j]=zs[i-j]+(cs[m-j]*zs[i]);
    return zs;
  }

  R calc(const VR &A,long long n){
    assert((int)A.size()==m);
    VR res(rs[0]);
    for(int i=0;n;i++,n>>=1){
      if(i>=(int)rs.size())
        rs.emplace_back(merge(rs[i-1],rs[i-1]));
      if(~n&1) continue;
      res=merge(res,rs[i]);
    }
    R ans=R::add_identity();
    for(int i=1;i<=m;i++) ans=ans+(res[i]*A[i-1]);
    return ans;
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#include "../mod/mint.cpp"
#undef call_from_test

//INSERT ABOVE HERE
signed TDPC_F(){
  using ll = long long;
  int n;
  ll k;
  scanf("%d %lld",&n,&k);

  using M = Mint<int>;
  vector<M> as(n,1),cs(n,1);
  Kitamasa<M> fib(cs);

  printf("%d\n",fib.calc(as,--k).v);
  return 0;
}
/*
  verified on 2019/12/10
  https://atcoder.jp/contests/tdpc/tasks/tdpc_fibonacci
*/

signed ABC009_D(){
  int k,m;
  scanf("%d %d",&k,&m);

  struct M{
    uint32_t v;
    M(){*this=add_identity();}
    M(uint32_t v):v(v){}
    M operator+(const M &a)const{return M(v^a.v);}
    M operator*(const M &a)const{return M(v&a.v);}
    static M add_identity(){return M(0);}
    static M mul_identity(){return M(~0u);}
  };

  vector<M> as(k),cs(k);
  for(int i=0;i<k;i++) scanf("%u",&as[i].v);
  for(int i=0;i<k;i++) scanf("%u",&cs[k-(i+1)].v);
  Kitamasa<M> v(cs);

  printf("%u\n",v.calc(as,--m).v);
  return 0;
}
/*
  verified on 2019/12/10
  https://atcoder.jp/contests/abc009/tasks/abc009_4
*/

signed main(){
  //TDPC_F();
  //ABC009_D();
  return 0;
}
#endif

#undef call_from_test

signed main(){
  using M = Mint<int, 17>;
  const int n = 4;
  vector<M> as(n,0),cs(n,1);
  as[n-1]=1;
  Kitamasa<M> fib(cs);

  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    long long p;
    cin>>p;
    cout<<fib.calc(as,p-1)<<"\n";
  }
  return 0;
}