結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー |
![]() |
提出日時 | 2020-02-21 17:15:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,767 bytes |
コンパイル時間 | 2,202 ms |
コンパイル使用メモリ | 201,668 KB |
最終ジャッジ日時 | 2025-01-09 01:19:16 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 8 |
ソースコード
#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 HEREstruct FastIO{FastIO(){cin.tie(0);ios::sync_with_stdio(0);}}fastio_beet;//END CUT HERE#ifndef call_from_testsigned main(){return 0;}#endif#ifndef call_from_test#include<bits/stdc++.h>using namespace std;#endif//BEGIN CUT HEREtemplate<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 HEREsigned 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/12https://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 HEREtemplate<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 HEREsigned 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/10https://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/10https://atcoder.jp/contests/abc009/tasks/abc009_4*/signed main(){//TDPC_F();//ABC009_D();return 0;}#endif#undef call_from_testsigned 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)<<endl;}return 0;}