結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | smiken_61 |
提出日時 | 2022-02-27 23:56:57 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,157 ms / 2,000 ms |
コード長 | 12,119 bytes |
コンパイル時間 | 4,874 ms |
コンパイル使用メモリ | 277,892 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 02:48:25 |
合計ジャッジ時間 | 27,524 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,099 ms
6,812 KB |
testcase_01 | AC | 1,103 ms
6,940 KB |
testcase_02 | AC | 1,109 ms
6,944 KB |
testcase_03 | AC | 1,157 ms
6,940 KB |
testcase_04 | AC | 1,148 ms
6,944 KB |
testcase_05 | AC | 1,116 ms
6,940 KB |
testcase_06 | AC | 1,121 ms
6,944 KB |
testcase_07 | AC | 1,107 ms
6,944 KB |
testcase_08 | AC | 1,109 ms
6,944 KB |
testcase_09 | AC | 1,091 ms
6,940 KB |
testcase_10 | AC | 1,130 ms
6,944 KB |
testcase_11 | AC | 1,126 ms
6,940 KB |
testcase_12 | AC | 1,134 ms
6,944 KB |
testcase_13 | AC | 1,123 ms
6,940 KB |
testcase_14 | AC | 1,138 ms
6,940 KB |
testcase_15 | AC | 1,113 ms
6,944 KB |
testcase_16 | AC | 1,038 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; // tabaicho see https://boostjp.github.io/tips/multiprec-int.html // #include <boost/multiprecision/cpp_int.hpp> // using namespace boost::multiprecision; // cpp_int // int128_t // int256_t // int512_t // int1024_t // uint128_t // uint256_t // uint512_t // uint1024_t #define int long long #define inf 1000000007 // #define inf 998244353 #define pa pair<int,int> #define ppa pair<pa,pa> #define ll long long #define PI 3.14159265358979323846 #define mp make_pair #define pb push_back #define EPS (1e-8) using namespace std; int dx[8]={0,1,0,-1,1,1,-1,-1}; int dy[8]={1,0,-1,0,-1,1,1,-1}; class pa3{ public: int x; int y,z; pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {} bool operator < (const pa3 &p) const{ if(x!=p.x) return x<p.x; if(y!=p.y) return y<p.y; return z<p.z; //return x != p.x ? x<p.x: y<p.y; } bool operator > (const pa3 &p) const{ if(x!=p.x) return x>p.x; if(y!=p.y) return y>p.y; return z>p.z; //return x != p.x ? x<p.x: y<p.y; } bool operator == (const pa3 &p) const{ return x==p.x && y==p.y && z==p.z; } bool operator != (const pa3 &p) const{ return !( x==p.x && y==p.y && z==p.z); } }; class pa4{ public: int x; int y,z,w; pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {} bool operator < (const pa4 &p) const{ if(x!=p.x) return x<p.x; if(y!=p.y) return y<p.y; if(z!=p.z)return z<p.z; return w<p.w; //return x != p.x ? x<p.x: y<p.y; } bool operator > (const pa4 &p) const{ if(x!=p.x) return x>p.x; if(y!=p.y) return y>p.y; if(z!=p.z)return z>p.z; return w>p.w; //return x != p.x ? x<p.x: y<p.y; } bool operator == (const pa4 &p) const{ return x==p.x && y==p.y && z==p.z &&w==p.w; } }; class pa2{ public: int x,y; pa2(int x=0,int y=0):x(x),y(y) {} pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);} pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);} bool operator < (const pa2 &p) const{ return y != p.y ? y<p.y: x<p.x; } bool operator > (const pa2 &p) const{ return x != p.x ? x<p.x: y<p.y; } bool operator == (const pa2 &p) const{ return abs(x-p.x)==0 && abs(y-p.y)==0; } bool operator != (const pa2 &p) const{ return !(abs(x-p.x)==0 && abs(y-p.y)==0); } }; string itos( int i ) { ostringstream s ; s << i ; return s.str() ; } int Gcd(int v,int b){ if(v==0) return b; if(b==0) return v; if(v>b) return Gcd(b,v); if(v==b) return b; if(b%v==0) return v; return Gcd(v,b%v); } int extgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int d = extgcd(b, a%b, y, x); y -= a/b * x; return d; } pa operator+(const pa & l,const pa & r) { return {l.first+r.first,l.second+r.second}; } pa operator-(const pa & l,const pa & r) { return {l.first-r.first,l.second-r.second}; } pair<double,double> operator-(const pair<double,double> & l,const pair<double,double> & r) { return {l.first-r.first,l.second-r.second}; } ostream& operator<<(ostream& os, const vector<int>& VEC){ for(auto v:VEC)os<<v<<" "; return os; } ostream& operator<<(ostream& os, const pair<double,double>& PAI){ os<<PAI.first<<" : "<<PAI.second; return os; } ostream& operator<<(ostream& os, const pa& PAI){ os<<PAI.first<<" : "<<PAI.second; return os; } ostream& operator<<(ostream& os, const pa3& PAI){ os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z; return os; } ostream& operator<<(ostream& os, const pa4& PAI){ os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z<<" : "<<PAI.w; return os; } ostream& operator<<(ostream& os, const vector<pa>& VEC){ for(auto v:VEC)os<<v<<" "; return os; } ostream& operator<<(ostream& os, const vector<pa3>& VEC){ for(auto v:VEC){ os<<v<<" "; os<<endl; } return os; } int beki(int wa,ll rr,int warukazu){ if(rr==0) return 1%warukazu; if(rr==1) return wa%warukazu; wa%=warukazu; if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu; ll zx=beki(wa,rr/2,warukazu); return (zx*zx)%warukazu; } int pr[2500002]; int inv[2500002]; //const int mod=998244353; const int mod=1000000007; int comb(int nn,int rr){ if(nn==-1&&rr==-1)return 1; if(rr<0 || rr>nn || nn<0) return 0; int r=pr[nn]*inv[rr]; r%=mod; r*=inv[nn-rr]; r%=mod; return r; } void gya(int ert){ pr[0]=1; for(int i=1;i<=ert;i++){ pr[i]=((ll)pr[i-1]*i)%mod; } inv[ert]=beki(pr[ert],mod-2,mod); for(int i=ert-1;i>=0;i--){ inv[i]=(ll)inv[i+1]*(i+1)%mod; } } int beki(int a,int b){ int ANS=1; int be=a%mod; while(b){ if(b&1){ ANS*=be; ANS%=mod; } be*=be; be%=mod; b/=2; } return ANS; } // cin.tie(0); // ios::sync_with_stdio(false); //priority_queue<pa3,vector<pa3>,greater<pa3>> pq; //sort(ve.begin(),ve.end(),greater<int>()); // mt19937(clock_per_sec); // mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ; // a,b,c : positive int a*b<=c <=> a<=c/b // auto dfs=[&](auto &&self,int r,int p)->int{ // }; class Point{ public: double x,y; Point(double x=0,double y=0):x(x),y(y) {} Point operator + (Point p) {return Point(x+p.x,y+p.y);} Point operator - (Point p) {return Point(x-p.x,y-p.y);} Point operator * (double a) {return Point(x*a,y*a);} Point operator / (double a) {return Point(x/a,y/a);} double absv() {return sqrt(norm());} double norm() {return x*x+y*y;} bool operator < (const Point &p) const{ return x != p.x ? x<p.x: y<p.y; } bool operator == (const Point &p) const{ return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS; } }; class Line{ public: // y=ax+b double a; double b; Line(double a=0,double b=0):a(a),b(b) {} double eval(double x){return a*x+b;} bool operator < (const Line &p) const{ return abs(a-p.a)>EPS ? a<p.a: b<p.b; } }; Point intersect_line(Line A,Line B){ double x=(B.b-A.b)/(A.a-B.a); return Point(x,A.eval(x)); } Line line_from_2_Point(Point A,Point B){ // line which through A,B double a=(B.y-A.y)/(B.x-A.x); return Line(a,A.y-a*A.x); } struct Segmin{ // 1 // 2 3 // 4 5 6 7 private: public: // (1<<15)=32768 // 1<<16 = 65536 // 1<<17 = 131072 // 1<<18 = 262144 int cor=(1<<19); vector<pa> vec; void shoki1(){ vec.resize(2*cor+3, mp(inf*2000000000ll*2ll,0)); for(int i=cor;i<2*cor;i++)vec[i].second=i-cor; } void shoki2(){ for(int i=cor-1;i>0;i--) { if(vec[2*i].first<=vec[2*i+1].first) vec[i]=vec[2*i]; else vec[i]=vec[2*i+1]; } } void updadd(int x,int w){ //x 項目に w加算 x+=cor; vec[x].first+=w; x/=2; while(x){ if(vec[2*x].first<=vec[2*x+1].first) vec[x]=vec[2*x]; else vec[x]=vec[2*x+1]; x/=2; } } void updchan(int x,int w){ //x項目をwに変更 x+=cor; vec[x].first=w; x/=2; while(x){ if(vec[2*x].first<=vec[2*x+1].first) vec[x]=vec[2*x]; else vec[x]=vec[2*x+1]; x/=2; } } // [a,b) // k-th node // k no kukanha [l,r) pa segmin(int a,int b){ a+=cor; b+=cor; pa ans=mp(inf*2000000000ll*2ll,-1); while(a<b){ if(a&1){ ans=min(ans,vec[a]); a++; } if(b&1){ b--; ans=min(ans,vec[b]); } a/=2; b/=2; } return ans; } }; using fps=vector<long long>; fps mul(fps x,fps y){ int xl=x.size(); int yl=y.size(); vector<long long> ans(xl+yl-1,0); for(int i=0;i<xl;i++)for(int j=0;j<yl;j++){ ans[i+j]+=x[i]*y[j]%mod; if(ans[i+j]>=mod)ans[i+j]-=mod; } return ans; } vector<long long>first_terms_by_FPS(fps bunsi,fps bunbo){ int a=bunsi.size(); int b=bunbo.size(); assert(a<b); assert(bunbo[0]!=0); if(bunbo[0]!=1){ int h=beki(bunbo[0],mod-2); for(auto &v:bunsi)v=v*h%mod; for(auto &v:bunbo)v=v*h%mod; } while(a!=b-1){ a++; bunsi.pb(0); } for(int i=1;i<a;i++){ for(int j=i-1;j>=0;j--){ bunsi[i]+=mod-bunbo[i-j]*bunsi[j]%mod; if(bunsi[i]>=mod)bunsi[i]-=mod; } } return bunsi; } // A[0],A[1],A[2],..,A[k-1] = first k terms of sequence // P[0]*A[n] + P[1]*A[n-1] + P[2]*A[n-2] + P[3]*A[n-3] + ... + P[k]A[n-k] = 0 // k>=1 // P[0]!=0 P.back()!=0 // return <bunsi,bunbo> // O(klogk) pair<fps,fps> get_fps_form_linear(vector<long long>A,vector<long long>P){ int k=A.size(); int l=P.size(); assert(k+1==l); fps e=mul(A,P); for(int i=0;i<k;i++)e.pop_back(); return mp(e,P); } int BM2(fps p,fps q,int k){ while(k){ while(q.size()&&q.back()==0)q.pop_back(); while(p.size()&&p.back()==0)p.pop_back(); int pl=p.size(); int ql=q.size(); if(pl==0)return 0; fps qm=q; for(int i=1;i<ql;i+=2)if(qm[i])qm[i]=mod-qm[i]; fps e=mul(q,qm); // s/t fps s,t; for(int i=0;i<(int)e.size();i+=2)t.pb(e[i]); e=mul(p,qm); if(k%2==0){ for(int i=0;i<(int)e.size();i+=2)s.pb(e[i]); } else{ for(int i=1;i<(int)e.size();i+=2)s.pb(e[i]); } swap(s,p); swap(t,q); k/=2; } return p[0]*beki(q[0],mod-2,mod)%mod; } int BM(fps p,fps q,int k){ int ps=p.size(); int qs=q.size(); while(k){ while(qs>0&&q.back()==0)q.pop_back(),qs--; while(ps>0&&p.back()==0)p.pop_back(),ps--; /* int pl=p.size(); int ql=q.size(); */ if(ps==0)return 0; fps qm=q; for(int i=1;i<qs;i+=2)if(qm[i])qm[i]=mod-qm[i]; //fps e=mul(q,qm); int es=qs+qs-1; // s/t fps s,t; t.resize(qs); for(int i=0;i<qs;i++)for(int j=(i&1);j<qs;j+=2){ t[(i+j)/2]+=q[i]*qm[j]%mod; if(t[(i+j)/2]>=mod)t[(i+j)/2]-=mod; } /* for(int i=0;i<es;i+=2)t.pb(e[i]); */ int ts=(es+1)/2; //fps e=mul(p,qm); es=ps+qs-1; int ss=0; if(k%2==0){ s.resize((es+1)/2); for(int i=0;i<ps;i++)for(int j=(i&1);j<qs;j+=2){ s[(i+j)/2]+=p[i]*qm[j]%mod; if(s[(i+j)/2]>=mod)s[(i+j)/2]-=mod; } //for(int i=0;i<es;i+=2)s.pb(e[i]); ss=(es+1)/2; } else{ s.resize(es/2); for(int i=0;i<ps;i++)for(int j=1-(i&1);j<qs;j+=2){ s[(i+j)/2]+=p[i]*qm[j]%mod; if(s[(i+j)/2]>=mod)s[(i+j)/2]-=mod; } //for(int i=1;i<es;i+=2)s.pb(e[i]); ss=es/2; } ps=ss,qs=ts; swap(s,p); swap(t,q); k/=2; } return p[0]*beki(q[0],mod-2,mod)%mod; } void solve(){ int p; cin>>p; vector<int>ve={0,1}; fps bunbo={1,mod-p,mod-1}; fps bunsi=get_fps_form_linear(ve,bunbo).first; bunbo=mul(bunbo,bunbo); bunsi=mul(bunsi,bunsi); int q; cin>>q; while(q--){ int a; cin>>a; a-=2; cout<<BM(bunsi,bunbo,a)<<endl; } } signed main(){ //mod=inf; cin.tie(0); ios::sync_with_stdio(false); int n=1; //cin>>n; for(int i=0;i<n;i++)solve(); return 0; }