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

提出ソース

結果

問題	No.980 Fibonacci Convolution Hard
ユーザー	🍮かんプリン
提出日時	2020-08-28 22:20:03
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	1,322 ms / 2,000 ms
コード長	18,257 bytes
コンパイル時間	2,717 ms
コンパイル使用メモリ	195,476 KB
実行使用メモリ	243,784 KB
最終ジャッジ日時	2024-11-14 01:10:27
合計ジャッジ時間	29,180 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,316 ms 243,784 KB
testcase_01	AC	1,312 ms 243,644 KB
testcase_02	AC	1,302 ms 243,500 KB
testcase_03	AC	1,311 ms 243,540 KB
testcase_04	AC	1,321 ms 243,664 KB
testcase_05	AC	1,310 ms 243,640 KB
testcase_06	AC	1,313 ms 243,652 KB
testcase_07	AC	1,313 ms 243,540 KB
testcase_08	AC	1,313 ms 243,540 KB
testcase_09	AC	1,312 ms 243,504 KB
testcase_10	AC	1,313 ms 243,676 KB
testcase_11	AC	1,313 ms 243,624 KB
testcase_12	AC	1,310 ms 243,496 KB
testcase_13	AC	1,309 ms 243,644 KB
testcase_14	AC	1,322 ms 243,604 KB
testcase_15	AC	1,317 ms 243,608 KB
testcase_16	AC	1,291 ms 243,624 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:528:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
  528 |         printf("%d\n",a[i].x);
      |                 ~^
      |                  |
      |                  int
      |                 %lld
main.cpp:526:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  526 |         scanf("%d",&i);
      |         ~~~~~^~~~~~~~~

ソースコード

raw source code

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

// 形式的冪級数
// root:原始根
// any:任意modで計算するか
// template < const int MOD , const int root = 3 , bool any = false>
// struct FormalPowerSeries {
// private:
//     using P = FormalPowerSeries< MOD, root, any >;
//     vector< long long > v;

//     //powMOD
//     long long powMOD(long long k, long long n, long long mod) const {
//         long long 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);
//             //while (this->size() && this->v.back() == 0) this->v.pop_back();
//             return *this;
//         }
//     }

//     // a[0]は0でない
//     P &operator/=(const P &a) {
//         *this *= a.inverse();
//         return *this;
//     }

//     // f(x)^-1 定数項は0でない
//     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);
//     }

//     // f'(x)
//     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;
//     }

//     // ∫f(x)dx
//     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;
//     }

//     // log(f(x)) 定数項は1である
//     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();
//     }

//     // exp(f(x)) 定数項は0である
//     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);
//     }

//     // f(x)^k
//     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;
//     }
// };

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< int MOD >
struct mint {
public:
    long long x;
    mint(long long x = 0) :x((x %= MOD) < 0 ? x + MOD : x) {}
    mint(std::string &s) {
        long long z = 0;
        for (int i = 0; i < s.size(); i++) {
            z *= 10;
            z += s[i] - '0';
            z %= MOD;
        }
        this->x = z;
    }
    mint operator-() const {return mint() -= *this; }
    mint& operator+=(const mint &a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint &a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint &a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint& operator/=(const mint &a) {
        long long n = MOD - 2;
        mint u = 1, b = a;
        while (n > 0) {
            if (n & 1) {
                u *= b;
            }
            b *= b;
            n >>= 1;
        }
        return *this *= u;
    }
    mint operator+(const mint &a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint &a) const {
        mint res(*this);
        return res *= a;
    }
    mint operator/(const mint &a) const {
        mint res(*this);
        return res /= a;
    }
    friend std::ostream& operator<<(std::ostream &os, const mint &n) {
        return os << n.x;
    }
    friend std::istream &operator>>(std::istream &is, mint &n) {
        long long x;
        is >> x;
        n = mint(x);
        return is;
    }
    bool operator==(const mint &a) const {
        return this->x == a.x;
    }
    mint pow(long long k) const {
        mint ret = 1;
        mint p = this->x;
        while (k > 0) {
            if (k & 1) {
                ret *= p;
            }
            p *= p;
            k >>= 1;
        }
        return ret;
    }
};

// 形式的冪級数
// any:任意modで計算するか
template < const int MOD , bool any = false>
struct FormalPowerSeries {
private:
    using P = FormalPowerSeries< MOD, any >;

    template< int _MOD >
    void ntt(vector< mint < _MOD > >& a, bool inverse) {
        static vector< mint< _MOD > > dw(30), idw(30);
        if (dw[0] == 0) {
            mint< _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] = mint<_MOD>(1) / dw[i];
        }
        int n = a.size();
        assert((n & (n - 1)) == 0);
        if (not inverse) {
            for (int m = n; m >>= 1;) {
                mint< _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.x >= _MOD) x.x -= _MOD;
                        a[i].x = x.x + y.x, a[j].x = x.x + (_MOD - y.x);
                    }
                    w *= dw[__builtin_ctz(++k)];
                }
            }
        } else {
            for (int m = 1; m < n; m *= 2) {
                mint< _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].x = x.x + (_MOD - y.x), a[j] *= w;
                    }
                    w *= idw[__builtin_ctz(++k)];
                }
            }
        }
        auto c = mint<_MOD>(1) / mint< _MOD >(inverse ? n : 1);
        for (auto&& e : a) e *= c;
    }

    template< int _MOD >
    vector< mint< _MOD > > convolution(vector< mint< _MOD > > l, vector< mint< _MOD > > r) {
        if (l.empty() || 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]).x;
            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;
    }

public:
    FormalPowerSeries(int sz = 0) {
        this->a.resize(sz, 0);
    }
    
    vector<mint<MOD>> a;

    P &operator*=(const P &b) {
        if (!any) {
            this->a = convolution(this->a, b.a);
            return *this;
        }
        else {
            if (this->a.empty() || b.a.empty()) {
                this->a.clear();
                return *this;
            }
            int n = this->a.size(), m = b.a.size();
            static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617;
            using Mint0 = mint< mod0 >;
            using Mint1 = mint< mod1 >;
            using Mint2 = mint< 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] = this->a[i].x, l1[i] = this->a[i].x, l2[i] = this->a[i].x;
            for (int j = 0; j < m; ++j) r0[j] = b.a[j].x, r1[j] = b.a[j].x, r2[j] = b.a[j].x;
            l0 = convolution(l0,r0);
            l1 = convolution(l1,r1);
            l2 = convolution(l2,r2);
            this->a.resize(n + m - 1);
            static const Mint1 im0 = Mint1(1) / Mint1(mod0);
            static const Mint2 im1 = Mint2(1) / Mint2(mod1), im0m1 = im1 / mod0;
            static const mint<MOD> m0 = mod0, m0m1 = m0 * mod1;
            for (int i = 0; i < n + m - 1; ++i) {
                int y0 = l0[i].x;
                int y1 = (im0 * (l1[i] - y0)).x;
                int y2 = (im0m1 * (l2[i] - y0) - im1 * y1).x;
                this->a[i] = m0m1 * y2 + y0 + m0 * y1;
            }
            return *this;
        }
    }
    mint< MOD > &operator[](int x) {
        assert(0 <= x && x < (int)this->a.size());
        return a[x];
    }
};

// template < int MOD >
// vector< mint< MOD > > operator+(vector< mint< MOD > > l, vector< mint< MOD > > r) {
//     l.resize(max(l.size(),r.size()));
//     for(int i = 0; i < r.size(); i++) l[i] += r[i];
//     return l;
// }

// template < int MOD >
// vector< mint< MOD > > operator-(vector< mint< MOD > > l, vector< mint< MOD > > r) {
//     l.resize(max(l.size(),r.size()));
//     for(int i = 0; i < r.size(); i++) l[i] -= r[i];
//     return l;
// }

//////////////////////////////

// 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;
// }

/////////////////////////////////////////

// template < int MOD >
// vector< mint < MOD > > pre(const vector<mint < MOD >> &a, int sz) {
//     return vector< mint<MOD> >(a.begin(), a.begin() + min((int)a.size(), sz));
// }

// // f(x)^-1 定数項は0でない
// template < int MOD >
// vector<mint < MOD >> inverse(const vector<mint < MOD >> &a, int deg = -1) {
//     assert(a.size() != 0 && a[0].x != 0);
//     const int n = (int)a.size();
//     if(deg == -1) deg = n;
//     vector<mint<MOD>> ret(1);
//     ret[0] = mint<MOD>(1) / a[0];
//     for(int i = 1; i < deg; i <<= 1) {
//         ret = pre((ret + ret - ret * ret * pre(a,i << 1)),i << 1);
//     }
//     return pre(ret,deg);
// }

int main() {
    constexpr long long mod = 1e9 + 7;
    int p;
    cin >> p;
    int n = 2e6;
    FormalPowerSeries<mod,true> a(n);
    for (int i = 0; i < n; ++i) {
        if (i < 2) {
            a[i] = i;
        } else {
            a[i] = a[i - 1] * p + a[i - 2];
        }
    }
    a *= a;
    int q;
    cin >> q;
    while (q--) {
        int i;
        scanf("%d",&i);
        i -= 2;
        printf("%d\n",a[i].x);
    }
    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード