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

提出ソース

結果

問題	No.980 Fibonacci Convolution Hard
ユーザー	🍮かんプリン
提出日時	2020-08-28 22:26:21
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	1,475 ms / 2,000 ms
コード長	15,907 bytes
コンパイル時間	2,137 ms
コンパイル使用メモリ	190,736 KB
実行使用メモリ	309,404 KB
最終ジャッジ日時	2024-04-26 13:25:01
合計ジャッジ時間	30,383 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,367 ms 309,180 KB
testcase_01	AC	1,389 ms 309,272 KB
testcase_02	AC	1,370 ms 309,224 KB
testcase_03	AC	1,382 ms 309,324 KB
testcase_04	AC	1,388 ms 309,112 KB
testcase_05	AC	1,436 ms 309,284 KB
testcase_06	AC	1,363 ms 309,056 KB
testcase_07	AC	1,382 ms 309,404 KB
testcase_08	AC	1,385 ms 309,292 KB
testcase_09	AC	1,379 ms 309,224 KB
testcase_10	AC	1,452 ms 309,328 KB
testcase_11	AC	1,421 ms 309,220 KB
testcase_12	AC	1,475 ms 309,192 KB
testcase_13	AC	1,437 ms 309,284 KB
testcase_14	AC	1,408 ms 309,288 KB
testcase_15	AC	1,451 ms 309,284 KB
testcase_16	AC	1,374 ms 309,252 KB

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

コンパイルメッセージ

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

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 > > operator*(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;
}

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

template< int MOD >
vector< mint< MOD > > convolution(const vector< mint< MOD > >& l, const vector< mint< MOD > >& 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 = 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] = l[i].x, l1[i] = l[i].x, l2[i] = l[i].x;
    for (int j = 0; j < m; ++j) r0[j] = r[j].x, r1[j] = r[j].x, r2[j] = r[j].x;
    l0 = l0 * r0, l1 = l1 * r1, l2 = l2 * r2;
    vector< mint < MOD > > res(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;
        res[i] = m0m1 * y2 + y0 + m0 * y1;
    }
    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;
    vector< mint<mod> > 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 = convolution(a,a);
    int q;
    cin >> q;
    while (q--) {
        int i;
        scanf("%d",&i);
        i -= 2;
        printf("%d\n",a[i].x);
    }
    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード