#541466 (C++11) No.980 Fibonacci Convolution Hard

• 問題: No.980 Fibonacci Convolution Hard
• ユーザー: 🍮かんプリン
• 提出日時: 2020-08-28 17:39:23
• 言語: C++11 (gcc 11.4.0)
• 結果: TLE
• 実行時間: -
• コード長: 8,654 bytes
• コンパイル時間: 1,765 ms
• コンパイル使用メモリ: 173,368 KB
• 実行使用メモリ: 257,948 KB
• 最終ジャッジ日時: 2023-08-08 19:54:48
• 合計ジャッジ時間: 47,741 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-

ソースコード

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.08.28 17:39:17
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;




template < const int MOD , const int root = 3 , bool any = false>
struct FormalPowerSeries {
private:
    using P = FormalPowerSeries< MOD, root, any >;
    vector< long long > v;
    
    
    long long powMod(long long k, long long n, long long mod) const {
        ll x = 1;
        while (n > 0) {
            if (n & 1) {
                x = x * k % mod;
            }
            k = k * k % mod;
            n >>= 1;
        }
        return x;
    }
    void ntt(const bool rev = false) {
        unsigned int i, j, k, l, p, q, r, s;
        const unsigned int sz = this->v.size();
        if(sz == 1) return;
        vector<long long> a(sz);
        r = rev ? (MOD - 1 - (MOD - 1) / sz) : (MOD - 1) / sz;
        s = powMod(root, r, MOD);
        vector<unsigned int> kp(sz / 2 + 1, 1);
        for(i = 0; i < sz / 2; ++i) kp[i + 1] = (unsigned long long)kp[i] * s % MOD;
        for(i = 1, l = sz / 2; i < sz; i <<= 1, l >>= 1){
            for(j = 0, r = 0; j < l; ++j, r += i){
                for(k = 0, s = kp[i * j]; k < i; ++k){
                    p = this->v[k + r], q = this->v[k + r + sz / 2];
                    a[k + 2 * r] = (p + q) % MOD;
                    a[k + 2 * r + i] = (unsigned long long)((p - q + MOD) % MOD) * s % MOD;
                }
            }
            swap(this->v, a);
        }
        if(rev){
            s = powMod(sz,MOD-2,MOD);
            for(i = 0; i < sz; i++){ this->v[i] = (unsigned long long)this->v[i] * s % MOD; }
        }
    }
    inline P pre(int sz) const {
        return P(vector<long long>(this->v.begin(), this->v.begin() + min((int) this->v.size(), sz)));
    }
public:
    FormalPowerSeries(int sz = 0) {
        this->v.resize(sz, 0);
    }
    FormalPowerSeries(const vector<long long> &v) {
        this->v.resize(v.size());
        for (int i = 0; i < v.size(); i++) {
            this->v[i] = v[i];
        }
    }
    
    inline size_t size() const { return this->v.size(); }
    inline void resize(int x, long long val = 0) {
        assert(x >= 0);
        this->v.resize(x,val);
    }
    inline void set(int x, long long val) {
        assert(0 <= x && x < (int)v.size());
        this->v[x] = (val % MOD + MOD) % MOD;
    }
    P operator+(const P &a) const { return P(*this) += a; }
    P operator+(const long long a) const { return P(*this) += a; }
    P operator-(const P &a) const { return P(*this) -= a; }
    P operator*(const P &a) const { return P(*this) *= a; }
    P operator*(const long long a) const { return P(*this) *= a; }
    P operator/(const P &a) const { return P(*this) /= a; }
    P &operator+=(const P &a) {
        if (a.size() > this->v.size()) this->v.resize(a.size(), 0);
        for (int i = 0; i < a.size(); i++) this->v[i] += a[i], this->v[i] %= MOD;
        return *this;
    }
    P &operator+=(const long long a) {
        if (this->v.size() == 0) this->v.resize(1,(a % MOD + MOD) % MOD);
        else this->v[0] += a, this->v[0] %= MOD;
        return *this;
    }
    P &operator-=(const P &a) {
        if (a.size() > this->v.size()) this->v.resize(a.size(), 0);
        for (int i = 0; i < a.size(); i++) this->v[i] = this->v[i] - a[i] + MOD, this->v[i] %= MOD;
        while (this->size() && this->v.back() == 0) this->v.pop_back();
        return *this;
    }
    P &operator*=(const long long a) {
        for (int i = 0; i < this->v.size(); i++) this->v[i] *= a, this->v[i] %= MOD;
        return *this;
    }
    P &operator*=(const P &a) {
        if (this->v.empty() || (int)a.size() == 0) {
            this->v.clear();
            return *this;
        }
        if (any) {
            int n = this->v.size(), m = a.size();
            static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617;
            using T0 = FormalPowerSeries<mod0,3>;
            using T1 = FormalPowerSeries<mod1,3>;
            using T2 = FormalPowerSeries<mod2,5>;
            T0 l0(n), r0(m);
            T1 l1(n), r1(m);
            T2 l2(n), r2(m);
            for (int i = 0; i < n; ++i) l0.set(i,this->v[i]), l1.set(i,this->v[i]), l2.set(i,this->v[i]);
            for (int j = 0; j < m; ++j) r0.set(j,a[j]), r1.set(j,a[j]), r2.set(j,a[j]);
            l0 = l0 * r0, l1 = l1 * r1, l2 = l2 * r2;
            this->v.resize(n + m - 1);
            static const long long im0 = powMod(mod0, mod1-2, mod1);
            static const long long im1 = powMod(mod1, mod2-2, mod2), im0m1 = im1 * powMod(mod0, mod2-2, mod2) % mod2;
            static const long long m0 = mod0 % MOD, m0m1 = m0 * mod1 % MOD;
            for (int i = 0; i < n + m - 1; ++i) {
                int y0 = l0[i];
                int y1 = (im0 * (l1[i] - y0 + mod1)) % mod1;
                int y2 = (im0m1 * (l2[i] - y0 + mod2) % mod2 - im1 * y1 % mod2 + mod2) % mod2;
                this->v[i] = (y0 + m0 * y1 % MOD + m0m1 * y2 % MOD) % MOD;
            }
            return *this;
        }
        else {
            const int sz = (int)this->v.size() + (int)a.size() - 1;
            int t = 1;
            while(t < sz){ t <<= 1; }
            P A(t); this->v.resize(t,0);
            for(int i = 0; i < (int)a.size(); i++){ A.set(i,a[i]); }
            this->ntt(), A.ntt();
            for (int i = 0; i < t; i++){ this->v[i] = (unsigned long long)this->v[i] * A[i] % MOD; }
            this->ntt(true);
            this->v.resize(sz);
            
            return *this;
        }
    }
    
    P &operator/=(const P &a) {
        *this *= a.inverse();
        return *this;
    }
    
    P inverse(int deg = -1) const {
        assert(this->v.size() != 0 && this->v[0] != 0);
        const int n = (int)this->v.size();
        if(deg == -1) deg = n;
        P ret(1);
        ret.set(0,powMod(this->v[0],MOD-2,MOD)); 
        for(int i = 1; i < deg; i <<= 1) {
            ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);
        }
        return ret.pre(deg);
    }
    
    P differential() const {
        const int n = (int) this->v.size();
        P ret(max(0, n - 1));
        for(int i = 1; i < n; i++) ret.set(i-1,this->v[i] * i);
        return ret;
    }
    
    P integral() const {
        const int n = (int) this->v.size();
        P ret(n + 1);
        for(int i = 0; i < n; i++) ret.set(i + 1,this->v[i] * powMod(i + 1,MOD-2,MOD));
        return ret;
    }
    
    
    P log(int deg = -1) const {
        assert(this->v.size() != 0 && this->v[0] == 1);
        const int n = (int)this->v.size();
        if(deg == -1) deg = n;
        return (this->differential() * this->inverse(deg)).pre(deg - 1).integral();
    }
    
    P exp(int deg = -1) const {
        if (this->v.size() == 0) return P(0);
        assert(this->v[0] == 0);
        const int n = (int) this->v.size();
        if(deg == -1) deg = n;
        P ret(1);
        ret.set(0,1);
        for(int i = 1; i < deg; i <<= 1) {
            ret = (ret * (pre(i << 1) + 1 - ret.log(i << 1))).pre(i << 1);
        }
        return ret.pre(deg);
    }
    
    P pow(long long k, int deg = -1) const {
        const int n = (int) this->v.size();
        if(deg == -1) deg = n;
        for(int i = 0; i < n; i++) {
            if(this->v[i] != 0) {
                long long rev = powMod(this->v[i],MOD-2,MOD);
                P C = *this * rev;
                P D(n - i);
                for(int j = i; j < n; j++) D.set(j - i,C[j]);
                D = (D.log() * k).exp() * powMod(this->v[i],k,MOD);
                P E(deg);
                if(i * k > deg) return E;
                auto S = i * k;
                for(int j = 0; j + S < deg && j < D.size(); j++) E.set(j + S,D[j]);
                return E;
            }
        }
        return *this;
    }
    inline long long operator[](int x) const {
        assert(0 <= x && x < (int)this->v.size());
        return v[x];
    }
    friend std::ostream &operator<<(std::ostream &os, const P &p) {
        os << "[ ";
        for (int i = 0; i < (int)p.size(); i++) {
            os << p[i] << " ";
        }
        os << "]";
        return os;
    }
};
int main() {
    int p,q;cin >> p >> q;
    const int max_query = 2 * 1000000;
    const long long MOD = 1e9 + 7;
    FormalPowerSeries<MOD,3,true> a(max_query);
    a.set(0,0);
    a.set(1,1);
    long long a1 = 0, a2 = 1;
    for (int i = 2; i < max_query; i++) {
        a.set(i,(a2 * p + a1) % MOD);
        a1 = a2;
        a2 = a[i];
    }
    a *= a;
    for (int i = 0; i < q; i++) {
        int x;scanf("%d",&x);
        printf("\t%d\n",a[x-2]);
    }
    return 0;
}