#424486 (C++14) No.980 Fibonacci Convolution Hard

提出ソース
結果

問題	No.980 Fibonacci Convolution Hard
ユーザー	iiljj
提出日時	2020-02-01 00:55:39
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	839 ms / 2,000 ms
コード長	14,517 bytes
コンパイル時間	2,770 ms
コンパイル使用メモリ	208,248 KB
実行使用メモリ	77,440 KB
最終ジャッジ日時	2024-09-17 14:52:20
合計ジャッジ時間	19,607 ms
ジャッジサーバーID （参考情報）	judge6 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	786 ms 77,440 KB
testcase_01	AC	789 ms 77,312 KB
testcase_02	AC	806 ms 77,412 KB
testcase_03	AC	791 ms 77,312 KB
testcase_04	AC	832 ms 77,392 KB
testcase_05	AC	811 ms 77,312 KB
testcase_06	AC	813 ms 77,312 KB
testcase_07	AC	796 ms 77,312 KB
testcase_08	AC	827 ms 77,312 KB
testcase_09	AC	795 ms 77,440 KB
testcase_10	AC	806 ms 77,312 KB
testcase_11	AC	802 ms 77,368 KB
testcase_12	AC	802 ms 77,312 KB
testcase_13	AC	814 ms 77,312 KB
testcase_14	AC	819 ms 77,344 KB
testcase_15	AC	839 ms 77,312 KB
testcase_16	AC	797 ms 77,276 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
/* #region Head */

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;

#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))
#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))
#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))
#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))
#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))
#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define ALL(x) begin(x), end(x)
#define SIZE(x) ((ll)(x).size())
#define PREM(c)   \
    sort(all(c)); \
    for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))
#define UNIQ(v) v.erase(unique(ALL(v)), v.end());

constexpr ll INF = 1'010'000'000'000'000'017LL;
constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.14159265358979323846;

// vector入力
template <typename T>
istream &operator>>(istream &is, vc<T> &vec)
{
    for (T &x : vec)
        is >> x;
    return is;
}

// vector出力 (for dump)
template <typename T>
ostream &operator<<(ostream &os, vc<T> &vec)
{
    ll len = SIZE(vec);
    os << "{";
    for (int i = 0; i < len; i++)
        os << vec[i] << (i == len - 1 ? "" : ", ");
    os << "}";
    return os;
}

// vector出力 (inline)
template <typename T>
ostream &operator>>(ostream &os, vc<T> &vec)
{
    ll len = SIZE(vec);
    for (int i = 0; i < len; i++)
        os << vec[i] << (i == len - 1 ? "\n" : " ");
    return os;
}

// pair入力
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &pair_var)
{
    is >> pair_var.first >> pair_var.second;
    return is;
}

// pair出力
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &pair_var)
{
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

// map出力
template <typename T, typename U>
ostream &operator<<(ostream &os, map<T, U> &map_var)
{
    os << "{";
    REPI(itr, map_var)
    {
        os << *itr;
        itr++;
        if (itr != map_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}

// set 出力
template <typename T>
ostream &operator<<(ostream &os, set<T> &set_var)
{
    os << "{";
    REPI(itr, set_var)
    {
        os << *itr;
        itr++;
        if (itr != set_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}

// dump
#define DUMPOUT cerr
void dump_func()
{
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&... tail)
{
    DUMPOUT << head;
    if (sizeof...(Tail) > 0)
    {
        DUMPOUT << ", ";
    }
    dump_func(move(tail)...);
}

// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>>
bool chmax(T &xmax, const U &x, Comp comp = {})
{
    if (comp(xmax, x))
    {
        xmax = x;
        return true;
    }
    return false;
}

// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>>
bool chmin(T &xmin, const U &x, Comp comp = {})
{
    if (comp(x, xmin))
    {
        xmin = x;
        return true;
    }
    return false;
}

// ローカル用
#define DEBUG_

#ifdef DEBUG_
#define DEB
#define dump(...)                                                       \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                     \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \
            << endl                                                     \
            << "    ",                                                  \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif

struct AtCoderInitialize
{
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    AtCoderInitialize()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH)
            cout << unitbuf;
    }
} ATCODER_INITIALIZE;

/* #endregion */

/* #region ConvWithMint */
#define rep(i, b) REP(i, 0, b)
#define si(x) int(x.size())

//size of input must be a power of 2
//output of forward fmt is bit-reversed
//output elements are in the range [0,mod*4)
//input of inverse fmt should be bit-reversed
template <class mint>
void inplace_fmt(vector<mint> &f, bool inv)
{
    const int n = si(f);
    static const int L = 30;
    static mint g[L], ig[L], p2[L];
    if (g[0].v == 0)
    {
        rep(i, L)
        {
            mint w = -mint::root().pow(((mint::mod - 1) >> (i + 2)) * 3);
            g[i] = w;
            ig[i] = w.inv();
            p2[i] = mint(1 << i).inv();
        }
    }
    static constexpr uint mod2 = mint::mod * 2;
    if (!inv)
    {
        int b = n;
        if (b >>= 1)
        { //input:[0,mod)
            rep(i, b)
            {
                uint x = f[i + b].v;
                f[i + b].v = f[i].v + mint::mod - x;
                f[i].v += x;
            }
        }
        if (b >>= 1)
        { //input:[0,mod*2)
            mint p = 1;
            for (int i = 0, k = 0; i < n; i += b * 2)
            {
                REP(j, i, i + b)
                {
                    uint x = (f[j + b] * p).v;
                    //f[j].v=(f[j].v<mint::mod?f[j].v:f[j].v-mint::mod);
                    f[j + b].v = f[j].v + mint::mod - x;
                    f[j].v += x;
                }
                p *= g[__builtin_ctz(++k)];
            }
        }
        while (b)
        {
            if (b >>= 1)
            { //input:[0,mod*3)
                mint p = 1;
                for (int i = 0, k = 0; i < n; i += b * 2)
                {
                    REP(j, i, i + b)
                    {
                        uint x = (f[j + b] * p).v;
                        //f[j].v=(f[j].v<mint::mod?f[j].v:f[j].v-mint::mod);
                        f[j + b].v = f[j].v + mint::mod - x;
                        f[j].v += x;
                    }
                    p *= g[__builtin_ctz(++k)];
                }
            }
            if (b >>= 1)
            { //input:[0,mod*4)
                mint p = 1;
                for (int i = 0, k = 0; i < n; i += b * 2)
                {
                    REP(j, i, i + b)
                    {
                        uint x = (f[j + b] * p).v;
                        f[j].v = (f[j].v < mod2 ? f[j].v : f[j].v - mod2);
                        f[j + b].v = f[j].v + mint::mod - x;
                        f[j].v += x;
                    }
                    p *= g[__builtin_ctz(++k)];
                }
            }
        }
    }
    else
    {
        int b = 1;
        if (b < n / 2)
        { //input:[0,mod)
            mint p = 1;
            for (int i = 0, k = 0; i < n; i += b * 2)
            {
                REP(j, i, i + b)
                {
                    ull x = f[j].v + mint::mod - f[j + b].v;
                    f[j].v += f[j + b].v;
                    f[j + b].v = x * p.v % mint::mod;
                }
                p *= ig[__builtin_ctz(++k)];
            }
            b <<= 1;
        }
        for (; b < n / 2; b <<= 1)
        {
            mint p = 1;
            for (int i = 0, k = 0; i < n; i += b * 2)
            {
                REP(j, i, i + b / 2)
                { //input:[0,mod*2)
                    ull x = f[j].v + mod2 - f[j + b].v;
                    f[j].v += f[j + b].v;
                    f[j].v = (f[j].v) < mod2 ? f[j].v : f[j].v - mod2;
                    f[j + b].v = x * p.v % mint::mod;
                }
                REP(j, i + b / 2, i + b)
                { //input:[0,mod)
                    ull x = f[j].v + mint::mod - f[j + b].v;
                    f[j].v += f[j + b].v;
                    //f[j].v=(f[j].v)<mod2?f[j].v:f[j].v-mod2;
                    f[j + b].v = x * p.v % mint::mod;
                }
                p *= ig[__builtin_ctz(++k)];
            }
        }
        if (b < n)
        { //input:[0,mod*2)
            rep(i, b)
            {
                uint x = f[i + b].v;
                f[i + b].v = f[i].v + mod2 - x;
                f[i].v += x;
            }
        }
        mint z = p2[__lg(n)];
        rep(i, n) f[i] *= z;
    }
}

struct modinfo
{
    uint mod, root;
};
template <modinfo const &ref>
struct modular
{
    static constexpr uint const &mod = ref.mod;
    static modular root() { return modular(ref.root); }
    uint v;
    //modular(initializer_list<uint>ls):v(*ls.bg){}
    modular(ll vv = 0) { s(vv % mod + mod); }
    modular &s(uint vv)
    {
        v = vv < mod ? vv : vv - mod;
        return *this;
    }
    modular operator-() const { return modular() - *this; }
    modular &operator+=(const modular &rhs) { return s(v + rhs.v); }
    modular &operator-=(const modular &rhs) { return s(v + mod - rhs.v); }
    modular &operator*=(const modular &rhs)
    {
        v = ull(v) * rhs.v % mod;
        return *this;
    }
    modular &operator/=(const modular &rhs) { return *this *= rhs.inv(); }
    modular operator+(const modular &rhs) const { return modular(*this) += rhs; }
    modular operator-(const modular &rhs) const { return modular(*this) -= rhs; }
    modular operator*(const modular &rhs) const { return modular(*this) *= rhs; }
    modular operator/(const modular &rhs) const { return modular(*this) /= rhs; }
    modular pow(int n) const
    {
        modular res(1), x(*this);
        while (n)
        {
            if (n & 1)
                res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
    modular inv() const { return pow(mod - 2); }
    /*modular inv()const{
		int x,y;
		int g=extgcd(v,mod,x,y);
		assert(g==1);
		if(x<0)x+=mod;
		return modular(x);
	}*/
    friend modular operator+(int x, const modular &y)
    {
        return modular(x) + y;
    }
    friend modular operator-(int x, const modular &y)
    {
        return modular(x) - y;
    }
    friend modular operator*(int x, const modular &y)
    {
        return modular(x) * y;
    }
    friend modular operator/(int x, const modular &y)
    {
        return modular(x) / y;
    }
    friend ostream &operator<<(ostream &os, const modular &m)
    {
        return os << m.v;
    }
    friend istream &operator>>(istream &is, modular &m)
    {
        ll x;
        is >> x;
        m = modular(x);
        return is;
    }
    bool operator<(const modular &r) const { return v < r.v; }
    bool operator==(const modular &r) const { return v == r.v; }
    bool operator!=(const modular &r) const { return v != r.v; }
    explicit operator bool() const
    {
        return v;
    }
};

//59501818244292734739283969=5.95*10^25 までの値を正しく計算
//最終的な列の大きさが 2^24 までなら動く
//最終的な列の大きさが 2^20 以下のときは，下の 3 つの素数を使ったほうが速い（は？）
//VERIFY: yosupo
namespace arbitrary_convolution
{
constexpr modinfo base0{167772161, 3};  //2^25 * 5 + 1
constexpr modinfo base1{469762049, 3};  //2^26 * 7 + 1
constexpr modinfo base2{754974721, 11}; //2^24 * 45 + 1
//constexpr modinfo base0{1045430273,3};//2^20 * 997 + 1
//constexpr modinfo base1{1051721729,6};//2^20 * 1003 + 1
//constexpr modinfo base2{1053818881,7};//2^20 * 1005 + 1
using mint0 = modular<base0>;
using mint1 = modular<base1>;
using mint2 = modular<base2>;
template <class t, class mint>
vc<t> sub(const vc<mint> &x, const vc<mint> &y, bool same = false)
{
    int n = si(x) + si(y) - 1;
    int s = 1;
    while (s < n)
        s *= 2;
    vc<t> z(s);
    rep(i, si(x)) z[i] = x[i].v;
    inplace_fmt(z, false);
    if (!same)
    {
        vc<t> w(s);
        rep(i, si(y)) w[i] = y[i].v;
        inplace_fmt(w, false);
        rep(i, s) z[i] *= w[i];
    }
    else
    {
        rep(i, s) z[i] *= z[i];
    }
    inplace_fmt(z, true);
    z.resize(n);
    return z;
}
template <class mint>
vc<mint> multiply(const vc<mint> &x, const vc<mint> &y, bool same = false)
{
    auto d0 = sub<mint0>(x, y, same);
    auto d1 = sub<mint1>(x, y, same);
    auto d2 = sub<mint2>(x, y, same);
    int n = si(d0);
    vc<mint> res(n);
    static const mint1 r01 = mint1(mint0::mod).inv();
    static const mint2 r02 = mint2(mint0::mod).inv();
    static const mint2 r12 = mint2(mint1::mod).inv();
    static const mint2 r02r12 = r02 * r12;
    static const mint w1 = mint(mint0::mod);
    static const mint w2 = w1 * mint(mint1::mod);
    rep(i, n)
    {
        ull a = d0[i].v;
        ull b = (d1[i].v + mint1::mod - a) * r01.v % mint1::mod;
        ull c = ((d2[i].v + mint2::mod - a) * r02r12.v + (mint2::mod - b) * r12.v) % mint2::mod;
        res[i].v = (a + b * w1.v + c * w2.v) % mint::mod;
    }
    return res;
}
} // namespace arbitrary_convolution
using arbitrary_convolution::multiply;

template <typename T>
vector<T> add_to_vector(vector<T> &z, T v)
{
    z.push_back(v);
    return z;
}

template <typename T, typename... Args>
vector<T> add_to_vector(vector<T> &z, T v, Args... args)
{
    z.push_back(v);
    add_to_vector<T>(z, args...);
    return z;
}

template <typename T>
vector<T> make_vector(T v)
{
    vector<T> z;
    z.push_back(v);
    return z;
}

template <typename T, typename... Args>
vector<T> make_vector(T v, Args... args)
{
    vector<T> z;
    z.push_back(v);
    add_to_vector<T>(z, args...);
    return z;
}

constexpr modinfo base{1000000007, 0};
using mint = modular<base>;
/* #endregion */

/**
Problem
 */
void solve()
{
    ll p, Q;
    cin >> p >> Q;
    vll q(Q);
    cin >> q;

    // construct a
    ll n = 2e6 + 11;
    vc<mint> a(n, 0);
    a[0] = 0;
    a[1] = 1;
    REP(i, 2, n)
    {
        a[i] = (a[i - 1] * p) + a[i - 2];
    }

    vc<mint> ret = arbitrary_convolution::multiply(a, a, true);
    // dump(result);
    REP(i, 0, Q)
    {
        cout << ret[q[i] - 2] << '\n';
    }
}

/**
 * エントリポイント．
 * @return 0.
 */
int main()
{
    solve();
    return 0;
}
yukicoder

結果

テストケース

ソースコード
