結果

問題 No.658 テトラナッチ数列 Hard
ユーザー beetbeet
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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)<<endl;
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0