結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | fuppy_kyopro |
提出日時 | 2020-01-31 23:30:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,353 ms / 2,000 ms |
コード長 | 12,789 bytes |
コンパイル時間 | 2,686 ms |
コンパイル使用メモリ | 199,900 KB |
実行使用メモリ | 164,116 KB |
最終ジャッジ日時 | 2024-09-17 11:42:32 |
合計ジャッジ時間 | 28,445 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,278 ms
164,036 KB |
testcase_01 | AC | 1,280 ms
163,988 KB |
testcase_02 | AC | 1,291 ms
163,988 KB |
testcase_03 | AC | 1,312 ms
164,024 KB |
testcase_04 | AC | 1,291 ms
164,116 KB |
testcase_05 | AC | 1,281 ms
164,068 KB |
testcase_06 | AC | 1,300 ms
164,116 KB |
testcase_07 | AC | 1,305 ms
164,036 KB |
testcase_08 | AC | 1,315 ms
163,984 KB |
testcase_09 | AC | 1,287 ms
163,988 KB |
testcase_10 | AC | 1,353 ms
163,996 KB |
testcase_11 | AC | 1,306 ms
164,000 KB |
testcase_12 | AC | 1,303 ms
163,988 KB |
testcase_13 | AC | 1,340 ms
164,028 KB |
testcase_14 | AC | 1,295 ms
164,072 KB |
testcase_15 | AC | 1,302 ms
164,100 KB |
testcase_16 | AC | 1,265 ms
164,004 KB |
ソースコード
// #include <bits/stdc++.h> // //#include <unistd.h> // //#include <iostream> // using namespace std; // #define DEBUG(x) cerr<<#x<<": "<<x<<endl; // #define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl; // #define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;} // typedef long long ll; // #define int ll // #define vi vector<int> // #define vl vector<ll> // #define vii vector< vector<int> > // #define vll vector< vector<ll> > // #define vs vector<string> // #define pii pair<int,int> // #define pis pair<int,string> // #define psi pair<string,int> // #define pll pair<ll,ll> // template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); } // template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); } // template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; } // #define X first // #define Y second // #define rep(i,n) for(int i=0;i<(n);i++) // #define rep1(i,n) for(int i=1;i<=(n);i++) // #define rrep(i,n) for(int i=(n)-1;i>=0;i--) // #define rrep1(i,n) for(int i=(n);i>0;i--) // #define REP(i,a,b) for(int i=a;i<b;i++) // #define in(x, a, b) (a <= x && x < b) // #define all(c) c.begin(),c.end() // template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } // template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; } // #define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end()); // const ll inf = 1000000001; // const ll INF = (ll)1e18 + 1; // const long double pi = 3.1415926535897932384626433832795028841971L; // #define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl; // int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; // int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 }; // #define fio() cin.tie(0); ios::sync_with_stdio(false); // const ll MOD = 1000000007; // //const ll MOD = 998244353; // // #define mp make_pair // //#define endl '\n' // 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;} // namespace FFT{ // using dbl = long double; // struct num{ // dbl x,y; // num(){x=y=0;} // num(dbl x,dbl y):x(x),y(y){} // }; // inline num operator+(num a,num b){ // return num(a.x+b.x,a.y+b.y); // } // inline num operator-(num a,num b){ // return num(a.x-b.x,a.y-b.y); // } // inline num operator*(num a,num b){ // return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); // } // inline num conj(num a){ // return num(a.x,-a.y); // } // int base=1; // vector<num> rts={{0,0},{1,0}}; // vector<int> rev={0,1}; // const dbl PI=asinl(1)*2; // void ensure_base(int nbase){ // if(nbase<=base) return; // rev.resize(1<<nbase); // for(int i=0;i<(1<<nbase);i++) // rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1)); // rts.resize(1<<nbase); // while(base<nbase){ // dbl angle=2*PI/(1<<(base+1)); // for(int i=1<<(base-1);i<(1<<base);i++){ // rts[i<<1]=rts[i]; // dbl angle_i=angle*(2*i+1-(1<<base)); // rts[(i<<1)+1]=num(cos(angle_i),sin(angle_i)); // } // base++; // } // } // void fft(vector<num> &as){ // int n=as.size(); // assert((n&(n-1))==0); // int zeros=__builtin_ctz(n); // ensure_base(zeros); // int shift=base-zeros; // for(int i=0;i<n;i++) // if(i<(rev[i]>>shift)) // swap(as[i],as[rev[i]>>shift]); // for(int k=1;k<n;k<<=1){ // for(int i=0;i<n;i+=2*k){ // for(int j=0;j<k;j++){ // num z=as[i+j+k]*rts[j+k]; // as[i+j+k]=as[i+j]-z; // as[i+j]=as[i+j]+z; // } // } // } // } // template<typename T> // vector<long long> multiply(vector<T> &as,vector<T> &bs){ // int need=as.size()+bs.size()-1; // int nbase=0; // while((1<<nbase)<need) nbase++; // ensure_base(nbase); // int sz=1<<nbase; // vector<num> fa(sz); // for(int i=0;i<sz;i++){ // T x=(i<(int)as.size()?as[i]:0); // T y=(i<(int)bs.size()?bs[i]:0); // fa[i]=num(x,y); // } // fft(fa); // num r(0,-0.25/sz); // for(int i=0;i<=(sz>>1);i++){ // int j=(sz-i)&(sz-1); // num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r; // if(i!=j) // fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r; // fa[i]=z; // } // fft(fa); // vector<long long> res(need); // for(int i=0;i<need;i++) // res[i]=round(fa[i].x); // return res; // } // }; // template<typename T> // struct ArbitraryMod{ // using dbl=FFT::dbl; // using num=FFT::num; // vector<T> multiply(vector<T> as,vector<T> bs){ // int need=as.size()+bs.size()-1; // int sz=1; // while(sz<need) sz<<=1; // vector<num> fa(sz),fb(sz); // for(int i=0;i<(int)as.size();i++) // fa[i]=num(as[i].v&((1<<15)-1),as[i].v>>15); // for(int i=0;i<(int)bs.size();i++) // fb[i]=num(bs[i].v&((1<<15)-1),bs[i].v>>15); // fft(fa);fft(fb); // dbl ratio=0.25/sz; // num r2(0,-1),r3(ratio,0),r4(0,-ratio),r5(0,1); // for(int i=0;i<=(sz>>1);i++){ // int j=(sz-i)&(sz-1); // num a1=(fa[i]+conj(fa[j])); // num a2=(fa[i]-conj(fa[j]))*r2; // num b1=(fb[i]+conj(fb[j]))*r3; // num b2=(fb[i]-conj(fb[j]))*r4; // if(i!=j){ // num c1=(fa[j]+conj(fa[i])); // num c2=(fa[j]-conj(fa[i]))*r2; // num d1=(fb[j]+conj(fb[i]))*r3; // num d2=(fb[j]-conj(fb[i]))*r4; // fa[i]=c1*d1+c2*d2*r5; // fb[i]=c1*d2+c2*d1; // } // fa[j]=a1*b1+a2*b2*r5; // fb[j]=a1*b2+a2*b1; // } // fft(fa);fft(fb); // vector<T> cs(need); // using ll = long long; // for(int i=0;i<need;i++){ // ll aa=T(llround(fa[i].x)).v; // ll bb=T(llround(fb[i].x)).v; // ll cc=T(llround(fa[i].y)).v; // cs[i]=T(aa+(bb<<15)+(cc<<30)); // } // return cs; // } // }; // using modint = Mint<ll, MOD>; // int n = 2000001; // vector<modint> a(n); // vector<modint> b, c; // signed main() { // int p; // cin >> p; // a[0] = 0; // a[1] = 1; // REP(i, 2, n) a[i] = (a[i - 1] * p + a[i - 2]); // //DEBUG_VEC(a); // b = a; // ArbitraryMod<modint> fft; // c = fft.multiply(a, b); // int q; // cin >> q; // while (q--) { // int s; // cin >> s; // s -= 2; // cout << c[s] << endl; // } // } #include <bits/stdc++.h> using namespace std; #ifdef __linux__ #define getchar getchar_unlocked #define putchar putchar_unlocked #endif template <class Z> Z getint() { char c = getchar(); bool neg = c == '-'; Z res = neg ? 0 : c - '0'; while (isdigit(c = getchar())) res = res * 10 + (c - '0'); return neg ? -res : res; } template <class Z> void putint(Z a, char c = '\n') { if (a < 0) putchar('-'), a = -a; int d[40], i = 0; do d[i++] = a % 10; while (a /= 10); while (i--) putchar('0' + d[i]); putchar(c); } template <class T, class F = multiplies<T>> T power(T a, long long n, F op = multiplies<T>(), T e = {1}) { assert(n >= 0); T res = e; while (n) { if (n & 1) res = op(res, a); if (n >>= 1) a = op(a, a); } return res; } template <unsigned Mod> struct Modular { using M = Modular; unsigned v; Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {} M operator-() const { return M() -= *this; } M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; } M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; } M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; } M& operator/=(M r) { return *this *= power(r, Mod - 2); } friend M operator+(M l, M r) { return l += r; } friend M operator-(M l, M r) { return l -= r; } friend M operator*(M l, M r) { return l *= r; } friend M operator/(M l, M r) { return l /= r; } friend bool operator==(M l, M r) { return l.v == r.v; } }; template <unsigned Mod> void ntt(vector<Modular<Mod>>& a, bool inverse) { static vector<Modular<Mod>> dw(30), idw(30); if (dw[0] == 0) { Modular<Mod> root = 2; while (power(root, (Mod - 1) / 2) == 1) root += 1; for (int i = 0; i < 30; ++i) dw[i] = -power(root, (Mod - 1) >> (i + 2)), idw[i] = 1 / dw[i]; } int n = a.size(); assert((n & (n - 1)) == 0); if (not inverse) { for (int m = n; m >>= 1; ) { Modular<Mod> w = 1; for (int s = 0, k = 0; s < n; s += 2 * m) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j] * w; if (x.v >= Mod) x.v -= Mod; a[i].v = x.v + y.v, a[j].v = x.v + (Mod - y.v); } w *= dw[__builtin_ctz(++k)]; } } } else { for (int m = 1; m < n; m *= 2) { Modular<Mod> w = 1; for (int s = 0, k = 0; s < n; s += 2 * m) { for (int i = s, j = s + m; i < s + m; ++i, ++j) { auto x = a[i], y = a[j]; a[i] = x + y, a[j].v = x.v + (Mod - y.v), a[j] *= w; } w *= idw[__builtin_ctz(++k)]; } } } auto c = 1 / Modular<Mod>(inverse ? n : 1); for (auto&& e : a) e *= c; } template <unsigned Mod> vector<Modular<Mod>> operator*(vector<Modular<Mod>> l, vector<Modular<Mod>> r) { if (l.empty() or r.empty()) return {}; int n = l.size(), m = r.size(), sz = 1 << __lg(2 * (n + m - 1) - 1); if (min(n, m) < 30) { vector<long long> res(n + m - 1); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) res[i + j] += (l[i] * r[j]).v; return {begin(res), end(res)}; } bool eq = l == r; l.resize(sz), ntt(l, false); if (eq) r = l; else r.resize(sz), ntt(r, false); for (int i = 0; i < sz; ++i) l[i] *= r[i]; ntt(l, true), l.resize(n + m - 1); return l; } constexpr long long mod = 1e9 + 7; using Mint = Modular<mod>; vector<Mint> operator*(const vector<Mint>& l, const vector<Mint>& r) { if (l.empty() or r.empty()) return {}; int n = l.size(), m = r.size(); static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617; using Mint0 = Modular<mod0>; using Mint1 = Modular<mod1>; using Mint2 = Modular<mod2>; vector<Mint0> l0(n), r0(m); vector<Mint1> l1(n), r1(m); vector<Mint2> l2(n), r2(m); for (int i = 0; i < n; ++i) l0[i] = l[i].v, l1[i] = l[i].v, l2[i] = l[i].v; for (int j = 0; j < m; ++j) r0[j] = r[j].v, r1[j] = r[j].v, r2[j] = r[j].v; l0 = l0 * r0, l1 = l1 * r1, l2 = l2 * r2; vector<Mint> res(n + m - 1); static const Mint1 im0 = 1 / Mint1(mod0); static const Mint2 im1 = 1 / Mint2(mod1), im0m1 = im1 / mod0; static const Mint m0 = mod0, m0m1 = m0 * mod1; for (int i = 0; i < n + m - 1; ++i) { int y0 = l0[i].v; int y1 = (im0 * (l1[i] - y0)).v; int y2 = (im0m1 * (l2[i] - y0) - im1 * y1).v; res[i] = y0 + m0 * y1 + m0m1 * y2; } return res; } int main() { int p = getint<int>(); int n = 2000002; vector<Mint> a(n); a[0] = 0; a[1] = 1; for (int i = 2; i < n; i++) a[i] = a[i - 1] * p + a[i - 2]; vector<Mint> b = a; a = a * b; int q; cin >> q; while (q--) { int s; cin >> s; s -= 2; cout << a[s].v << '\n'; } }