結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | sugarrr |
提出日時 | 2020-07-15 15:02:13 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,365 bytes |
コンパイル時間 | 2,710 ms |
コンパイル使用メモリ | 165,804 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-05-07 22:29:19 |
合計ジャッジ時間 | 11,001 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 336 ms
18,944 KB |
ソースコード
//#include <bits/stdc++.h> #include "bits/stdc++.h" using namespace std; typedef long long ll; /* #include "boost/multiprecision/cpp_int.hpp" #include "boost/multiprecision/cpp_dec_float.hpp" namespace mp = boost::multiprecision; typedef mp::cpp_int LL; typedef mp::number<mp::cpp_dec_float<1024>> DD;// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする) */ typedef long double dd; #define i_7 (ll)(1E9+7) //#define i_7 998244353 #define i_5 i_7-2 ll mod(ll a){ ll c=a%i_7; if(c>=0)return c; return c+i_7; } typedef pair<ll,ll> l_l; typedef pair<dd,dd> d_d; ll inf=(ll)1E16; #define rep(i,l,r) for(ll i=l;i<=r;i++) #define rrep(i,r,l) for(ll i=r;i>=l;i--) #define pb push_back ll max(ll a,ll b){if(a<b)return b;else return a;} ll min(ll a,ll b){if(a>b)return b;else return a;} void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]); void Min(ll &pos,ll val){pos=min(pos,val);} void Add(ll &pos,ll val){pos=mod(pos+val);} dd EPS=1E-9; #define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define fi first #define se second //#define endl "\n" //インタラクティブで消す!!!!!!!!!!!!!!!!!!!!! #define SORT(v) sort(v.begin(),v.end()) #define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end()) #define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin()) #define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin()) template<class T,class S> inline bool chmax(T &a, S b) { if(a < b) { a = b; return true; } return false; } template<class T,class S> inline bool chmin(T &a, S b) { if(a > b) { a = b; return true; } return false; } void mod_print(ll k){ ll P=50000; rep(y,1,P){ ll x=mod(y*k); if(abs(x)<=P||x+P>=i_7){ if(x+P>=i_7){ x-=i_7; } cout<<x<<"/"<<y<<endl; //cout<<setprecision(5)<<(dd)x/(dd)y; return; } } cout<<"nun"<<endl; } #define all(c) c.begin(),c.end() typedef vector<ll> vl; ////////////////////////// //from KaedeTakagaki //from https://judge.yosupo.jp/submission/7396 template<const ll md> struct ntt{ inline void add(ll &a, ll b) { a += b; if(a >= md) a -= md; } inline void sub(ll &a, ll b) { a -= b; if(a < 0) a += md; } inline ll add2(ll a, ll b) { a += b; if(a >= md) a -= md; return a;} inline ll sub2(ll a, ll b) { a -= b; if(a < 0) a += md; return a;} inline ll mul(ll a, ll b) { return (ll)((ll)a*b%md); } inline ll power(ll a, long long b) { ll res = 1; while (b > 0) { if (b & 1) res = mul(res, a); a = mul(a, a); b >>= 1; } return res; } inline ll inv(ll a) { a %= md; if (a < 0) a += md; ll b = md, u = 0, v = 1; while (a) { ll t = b / a; b -= t * a; swap(a, b); u -= t * v; swap(u, v); } assert(b == 1); if (u < 0) u += md; return u; } ll max_base, root; vector<ll> dw, idw; ntt() { ll tmp = md - 1; max_base = 0; while (tmp % 2 == 0) { tmp /= 2; max_base++; } root = 2; while (power(root, (md-1)>>1) == 1) root++; dw.resize(max_base); idw.resize(max_base); rep(i,0,max_base-1){ sub(dw[i], power(root, (md-1) >> (i+2))); idw[i] = inv(dw[i]); } } void fft(vector<ll> &a, bool inv) { const ll n = a.size(); assert((n & (n - 1)) == 0); assert(__builtin_ctz(n) <= max_base); if(!inv){ for(ll m=n;m>>=1;){ ll w = 1; for(ll s=0,k=0; s<n; s += 2*m){ for(ll i=s, j=s+m ; i < s+m; ++i, ++j) { ll x = a[i], y = mul(a[j], w); a[j] = (x>=y?x-y:x+md-y); a[i] = (x+y>=md?x+y-md:x+y); } w = mul(w, dw[__builtin_ctz(++k)]); } } } else{ for(ll m=1;m<n;m*=2){ ll w = 1; for(ll s=0,k=0; s<n; s += 2*m){ for(ll i=s, j=s+m ; i < s+m; ++i, ++j) { ll x = a[i], y = a[j]; a[j] = (x>=y?x-y:x+md-y); a[j] = mul(a[j], w); a[i] = (x+y>=md?x+y-md:x+y); } w = mul(w, idw[__builtin_ctz(++k)]); } } } } vector<ll> multiply(vector<ll> a, vector<ll> b, ll eq = 0) { ll need = a.size() + b.size() - 1; ll nbase = 0; while ((1 << nbase) < need) nbase++; ll sz = 1 << nbase; a.resize(sz); b.resize(sz); fft(a, 0); if (eq) b = a; else fft(b, 0); ll inv_sz = inv(sz); for (ll i = 0; i < sz; i++) { a[i] = mul(mul(a[i], b[i]), inv_sz); } fft(a, 1); a.resize(need); return a; } vector<ll> square(vector<ll> a) { return multiply(a, a, 1); } }; /* 167772161; //= 2^25 * 5 + 1 469762049; //= 2^26 * 7 + 1 754974721; //= 2^24 * 45 + 1 1045430273; //= 2^20 * 997 + 1 1051721729; //= 2^20 * 1003 + 1 1053818881; //= 2^20 * 1005 + 1 */ template<const ll md> vector<ll> anyntt(vector<ll>&a, vector<ll>&b, ll eq = 0) { for(auto &x:a)if(x<0)x=mod(x); for(auto &x:b)if(x<0)x=mod(x); //今回は2^20以下だからこっちの方が速い (らしい) (:maroon_kansha:) const ll m1 = 167772161, m2 = 469762049, m3 = 754974721; ntt<m1>n1; ntt<m2>n2; ntt<m3>n3; ntt<md>nn; auto a1 = n1.multiply(a, b, eq); auto a2 = n2.multiply(a, b, eq); auto a3 = n3.multiply(a, b, eq); const ll n = a1.size(); vector<ll>ret(n); vector<ll>m; m = {m1, m2, m3}; vector<ll>r; r = {1, n2.inv(m1), n3.inv(n3.mul(m1, m2))}; ll mm = nn.mul(m1, m2); rep(i,0,n-1){ n2.add(a2[i], n2.sub2(m2, a1[i])); ll v1 = n2.mul(a2[i], r[1]); n3.add(a3[i], n3.sub2(m3, n3.add2(a1[i], n3.mul(m1, v1)))); ll v2 = n3.mul(a3[i], r[2]); nn.add(a1[i], nn.add2(nn.mul(m1, v1), nn.mul(mm, v2))); ret[i] = a1[i]; } return ret; } ll po(ll i,ll p){ if(p==0)return 1; else{ i=mod(i); if(p==1)return i; if(p%2==0)return po(mod(i*i),p/2); return mod(i*po(i,p-1)); } } ll bunbo(ll n){ return po(n,i_5); } //from maspy // https://atcoder.jp/contests/aising2020/submissions/15155062 ll coef_of_generating_function(vector<ll>P,vector<ll>Q,ll n){ //多項式P,Qについて、PをQで割ったときのx^nの係数をreturn //Pの次数はQより小さいことが必要。 for(auto &x:P)if(x<0)x=mod(x); for(auto &x:Q)if(x<0)x=mod(x); //Q[0]を1にする。 ll z=Q[0]; ll bz=bunbo(z); for(auto &x:P)x=mod(x*bz); for(auto &x:Q)x=mod(x*bz); ll sp=P.size(),sq=Q.size(); rep(zz,1,sq-sp-1)P.pb(0); while(n>0){ vector<ll>Q1(Q.size()); rep(i,0,Q.size()-1){ if(i%2==0){ Q1[i]=Q[i]; }else{ Q1[i]=mod(-Q[i]); } } auto np=anyntt<(ll)i_7>(P,Q1); auto nq=anyntt<(ll)i_7>(Q,Q1); P.clear();Q.clear(); for(ll i=n&1;i<=np.size()-1;i+=2)P.pb(np[i]); for(ll i=0; i<=nq.size()-1;i+=2)Q.pb(nq[i]); n/=2; } return P[0]; } /////////////////////// int main(){fastio ll p;cin>>p; vl a={0,0,1}; vl b={1,-p,-1}; b=anyntt<i_7>(b,b); ll N=2000050; ll c[N]; rep(i,0,N-1){ if(i<=3){ ll sum=0; if(i==2)sum=-1; rep(j,1,i){ Add(sum,c[j]*b[i-j]); } c[i]=mod(-sum); }else{ ll sum=0; rep(j,i-4,i){ Add(sum,c[j]*b[i-j]); } c[i]=mod(-sum); } } // rep(i,0,10)cout<<i<<":"<<c[i]<<endl; ll que;cin>>que; while(que--){ ll q;cin>>q;q-=2; // cout<<coef_of_generating_function(a,b,q)<<endl; cout<<c[q]<<endl; } return 0; }