#345052 (C++17) No.829 成長関数インフレ中

提出ソース

結果

問題	No.829 成長関数インフレ中
ユーザー	Suikaba
提出日時	2019-05-04 16:41:54
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	7,665 bytes
コンパイル時間	2,631 ms
コンパイル使用メモリ	225,824 KB
実行使用メモリ	20,400 KB
最終ジャッジ日時	2024-06-23 02:09:27
合計ジャッジ時間	9,735 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 10,624 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	54 ms 8,016 KB
testcase_13	AC	5 ms 5,376 KB
testcase_14	AC	35 ms 6,356 KB
testcase_15	AC	1,001 ms 8,784 KB
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-

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

ソースコード

raw source code

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

using ll = long long;

ll mod_inv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while(b > 0) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    return (u % m + m) % m;
}

ll mod_pow(ll x, ll n, ll m) {
    ll res = 1;
    while(n > 0) {
        if(n & 1) (res *= x) %= m;
        (x *= x) %= m;
        n >>= 1;
    }
    return res;
}

// solve: find x which statisfies (x mod m[i]) == u[i]
// require: m[i] are co-prime
ll garner(std::vector<ll> m, std::vector<ll> u, int mod) {
    const int n = m.size();
    std::vector<ll> inv_prod(n);
    for(int i = 1; i < n; ++i) {
        ll prod = m[0] % m[i];
        for(int j = 1; j < i; ++j) {
            prod = (prod * m[j]) % m[i];
        }
        inv_prod[i] = mod_inv(prod, m[i]);
    }

    std::vector<ll> v(n);
    v[0] = u[0];
    for(int i = 1; i < n; ++i) {
        ll tmp = v[i - 1];
        for(int j = i - 2; j >= 0; --j) {
            tmp = (tmp * m[j] + v[j]) % m[i];
        }
        v[i] = ((u[i] - tmp) * inv_prod[i]) % m[i];
        if(v[i] < 0) v[i] += m[i];
    }

    ll res = v[n - 1];
    for(int i = n - 2; i >= 0; --i) {
        res = (res * m[i] + v[i]) % mod;
    }
    return res;
}

template <int Mod, bool IsPrime = false>
class mod_int {
    using ll = long long;

public:
    constexpr mod_int() : n(0) {}
    constexpr mod_int(int n_) : n(n_) {
        if(n >= Mod)     n %= Mod;
        else if(n < 0) n = (n % Mod + Mod) % Mod;
    }
    constexpr mod_int(ll n_) : n(n_) { n = (n + Mod) % Mod; }

    constexpr operator int() const { return n; }
    constexpr operator ll() const  { return n; }

    constexpr bool operator==(mod_int const& other) const { return n == other.n; }
    constexpr mod_int& operator+=(mod_int const& other) {
        if((n += other.n) >= Mod) n -= Mod;
        return *this;
    }
    constexpr mod_int& operator-=(mod_int const& other) {
        if((n += Mod - other.n) >= Mod) n -= Mod;
        return *this;
    }
    constexpr mod_int& operator*=(mod_int const& other) {
        n = (unsigned long long)n * other.n % Mod;
        return *this;
    }
    constexpr typename std::enable_if<IsPrime, mod_int>::type& operator/=(mod_int const& other) {
        return *this *= other.inverse();
    }
    constexpr mod_int operator+(mod_int other) const { return mod_int(*this) += other; }
    constexpr mod_int operator-(mod_int other) const { return mod_int(*this) -= other; }
    constexpr mod_int operator*(mod_int other) const { return mod_int(*this) *= other; }
    constexpr mod_int operator/(mod_int other) const { return mod_int(*this) /= other; }

    constexpr typename std::enable_if<IsPrime, mod_int>::type inverse() const {
        ll a = n, b = Mod, u = 1, v = 0;
        while(b) {
            ll t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        return mod_int(u);
    }

private:
    ll n;
};

template <int Mod, bool IsPrime>
std::ostream& operator<<(std::ostream& os, mod_int<Mod, IsPrime> const& n) {
    os << (int)n;
    return os;
}

constexpr int default_mod = 1000000007;

template <int Mod = default_mod>
mod_int<Mod, true> fact(int n, bool inv) {
    static std::vector<mod_int<Mod, true>> v = {1};
    static std::vector<mod_int<Mod, true>> v2 = {1};
    if(n >= static_cast<int>(v.size())) {
        const int from = v.size(), to = n + 1024;
        v.reserve(to); v2.reserve(to);
        for(int i = from; i < to; ++i) {
            v.push_back(v.back() * mod_int<Mod, true>(i));
            v2.push_back(v2.back() / mod_int<Mod, true>(i));
        }
    }
    return (inv ? v2[n] : v[n]);
}

template <int Mod = default_mod>
mod_int<Mod, true> comb(int n, int r) { // nCr
    if(r < 0 || r > n) return 0;
    return fact<Mod>(n, false) * fact<Mod>(r, true) * fact<Mod>(n - r, true);
}

using mint = mod_int<default_mod, true>; // default

template <int Mod, int PrimitiveRoot>
class NTT {
public:
    // assertion: v.size() == 2 ^ m
    static std::vector<int> fft(std::vector<int> v, bool inv) {
        for(auto& x : v) x %= Mod;
        const int n = v.size();
        assert((n ^ (n & -n)) == 0);
        int ww = mod_pow(PrimitiveRoot, (Mod - 1) / n, Mod);
        if(inv) ww = mod_inv(ww, Mod);
        for(int m = n; m >= 2; m >>= 1) {
            const int mh = m >> 1;
            int w = 1;
            for(int i = 0; i < mh; ++i) {
                for(int j = i; j < n; j += m) {
                    const int k = j + mh;
                    int x = v[j] - v[k];
                    if(x < 0) x += Mod;
                    v[j] += - Mod + v[k];
                    if(v[j] < 0) v[j] += Mod;
                    v[k] = (1LL * w * x) % Mod;
                }
                w = (1LL * w * ww) % Mod;
            }
            ww = (1LL * ww * ww) % Mod;
        }

        int i = 0;
        for(int j = 1; j < n - 1; ++j) {
            for(int k = n >> 1; k > (i ^= k); k >>= 1);
            if(j < i) swap(v[i], v[j]);
        }
        if(inv) {
            const int inv_n = mod_inv(n, Mod);
            for(auto& x : v) {
                x = (1LL * x * inv_n) % Mod;
            }
        }
        return v;
    }
    static std::vector<int> convolution(std::vector<int> f, std::vector<int> g) {
        int sz = 1;
        const int m = f.size() + g.size() - 1;
        while(sz < m) sz *= 2;
        f.resize(sz), g.resize(sz);
        f = NTT::fft(std::move(f), false); g = NTT::fft(std::move(g), false);
        for(int i = 0; i < sz; ++i) {
            f[i] = (1LL * f[i] * g[i]) % Mod;
        }

        return NTT::fft(std::move(f), true);
    }

    static int get_mod() {
        return Mod;
    }
};

using NTT_1 = NTT<167772161, 3>;  // 5 * 2^25 + 1
using NTT_2 = NTT<469762049, 3>;  // 7 * 2^26 + 1
using NTT_3 = NTT<1224736769, 3>; // 73 * 2^24 + 1

void shrink(vector<int>& v) {
    if(!v.empty() && v.back() == 1) v.pop_back();
}

std::vector<int> mod_convolution(std::vector<int> f, std::vector<int> g, const int mod) {
    for(auto& x : f) x %= mod;
    for(auto& y : g) y %= mod;
    const auto v1 = NTT_1::convolution(f, g);
    const auto v2 = NTT_2::convolution(f, g);
    const auto v3 = NTT_3::convolution(f, g);

    vector<int> res(v1.size());
    vector<ll> m = {NTT_1::get_mod(), NTT_2::get_mod(), NTT_3::get_mod()};
    for(int i = 0; i < (int)v1.size(); ++i) {
        vector<ll> u = {v1[i], v2[i], v3[i]};
        res[i] = garner(m, u, mod);
    }
    shrink(res);

    return res;
}

constexpr int mod = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, b; cin >> n >> b;
    vector<int> c(n + 1);
    for(int i = 0; i < n; ++i) {
        int s; cin >> s;
        c[s] += 1;
    }
    auto v = c;
    for(int i = n - 1; i >= 0; --i) {
        v[i] += v[i + 1];
    }
    queue<vector<int>> que;
    for(int i = 0; i < n; ++i) {
        if(c[n - i - 1] == 0) continue;
        const auto a = fact(v[n - i - 1], false) * fact(v[n - i], true) * mint(c[n - i - 1]) / mint(v[n - i - 1]);
        const auto b_ = fact(v[n - i - 1], false) * fact(v[n - i], true) * mint(v[n - i]) / mint(v[n - i - 1]);
        que.push({(int)b_, (int)a});
    }
    while(que.size() > 1) {
        auto f = que.front();
        que.pop();
        auto g = que.front();
        que.pop();
        auto h = mod_convolution(move(f), move(g), mod);
        shrink(h);
        que.push(move(h));
    }

    auto f = que.front();
    mint ans = 0, base = 1;
    for(int i = 0; i <= n; ++i, base *= b) {
        ans += mint(i) * base * ((int)f.size() > i ? mint(f[i]) : mint(0));
    }
    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード