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

提出ソース

結果

問題	No.829 成長関数インフレ中
ユーザー	Pachicobue
提出日時	2018-12-06 17:47:43
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,790 bytes
コンパイル時間	1,550 ms
コンパイル使用メモリ	99,636 KB
実行使用メモリ	22,872 KB
最終ジャッジ日時	2023-10-13 17:24:21
合計ジャッジ時間	10,607 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 14,028 KB
testcase_01	AC	5 ms 9,736 KB
testcase_02	AC	5 ms 9,684 KB
testcase_03	AC	5 ms 9,660 KB
testcase_04	AC	4 ms 9,616 KB
testcase_05	AC	4 ms 9,684 KB
testcase_06	AC	5 ms 9,684 KB
testcase_07	AC	4 ms 9,864 KB
testcase_08	AC	4 ms 9,652 KB
testcase_09	AC	5 ms 9,664 KB
testcase_10	AC	5 ms 9,656 KB
testcase_11	AC	5 ms 9,608 KB
testcase_12	AC	29 ms 9,616 KB
testcase_13	AC	6 ms 9,640 KB
testcase_14	AC	20 ms 9,680 KB
testcase_15	AC	743 ms 13,004 KB
testcase_16	AC	1,556 ms 16,652 KB
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using ll = long long;
using ull = unsigned long long;
constexpr ll MOD = 1000000007;
constexpr int MAX = 200000;
int R[MAX];
ll fact[2 * MAX + 1];
ll inv[2 * MAX + 1];
constexpr std::size_t PC(ull v) { return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<std::size_t>(v * 0x0101010101010101ULL >> 56 & 0x7f); }
constexpr std::size_t LG(ull v) { return v == 0 ? 0 : (v--, v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PC(v)); }
constexpr ull SZ(const ull v) { return 1ULL << LG(v); }
template <typename T>
constexpr std::pair<T, T> extgcd(const T a, const T b)
{
    if (b == 0) { return std::pair<T, T>{1, 0}; }
    const auto p = extgcd(b, a % b);
    return {p.second, p.first - p.second * (a / b)};
}
template <typename T>
constexpr T inverse(const T a, const T mod = MOD) { return (mod + extgcd(a, mod).first % mod) % mod; }
template <typename T, T mod = 924844033, T root = 5>
class NumberTheoreticTransformation
{
public:
    static std::vector<T> convolute(const std::vector<T>& a, const std::vector<T>& b)  // ans[i] = \sum_{A+B = i} a[A]*b[B]
    {
        const std::size_t size = a.size() + b.size() - 1, t = (std::size_t)SZ(size);
        std::vector<T> A(t, 0), B(t, 0);
        for (std::size_t i = 0; i < a.size(); i++) { A[i] = a[i]; }
        for (std::size_t i = 0; i < b.size(); i++) { B[i] = b[i]; }
        ntt(A), ntt(B);
        for (std::size_t i = 0; i < t; i++) { A[i] = mul(A[i], B[i]); }
        ntt(A, true);
        A.resize(size);
        return A;
    }

private:
    NumberTheoreticTransformation() = delete;
    static T add(const T x, const T y) { return (x + y < mod) ? x + y : x + y - mod; }
    static T mul(const T x, const T y) { return (x * y) % mod; }
    static T power(const T x, const T n) { return n == 0 ? (T)1 : n % 2 == 1 ? mul(power(x, n - 1), x) : power(mul(x, x), n / 2); }
    static T inverse(const T x) { return power(x, mod - 2); }
    static void ntt(std::vector<T>& a, const bool rev = false)
    {
        const std::size_t size = a.size(), height = LG(size);
        for (std::size_t i = 0, j = 0; i < size; i++, j = 0) {
            for (std::size_t k = 0; k < height; k++) { j |= (i >> k & 1) << (height - 1 - k); }
            if (i < j) { std::swap(a[i], a[j]); }
        }
        for (std::size_t i = 1; i < size; i <<= 1) {
            T w = power(root, (mod - 1) / (i * 2));
            if (not rev) { w = inverse(w); }
            for (std::size_t j = 0; j < size; j += i * 2) {
                T wn = 1;
                for (std::size_t k = 0; k < i; k++, wn = mul(wn, w)) {
                    const T s = a[j + k + 0], t = mul(a[j + k + i], wn);
                    a[j + k + 0] = add(s, t), a[j + k + i] = add(s, mod - t);
                }
            }
        }
        if (not rev) { return; }
        const T v = inverse(size);
        for (std::size_t i = 0; i < size; i++) { a[i] = mul(a[i], v); }
    }
};
template <typename T>
class GarnerNumberTheoreticTransformation
{
public:
    static std::vector<T> convolute(const std::vector<T>& a, const std::vector<T>& b, const T mod)  // ans[i] = \sum_{A+B = i} a[A]*b[B]
    {
        const auto x = NTT1::convolute(a, b), y = NTT2::convolute(a, b), z = NTT3::convolute(a, b);
        const std::size_t size = x.size();
        std::vector<T> ans(size);
        const T mod1mod2_mod = mod1 * mod2 % mod;
        for (std::size_t i = 0; i < size; i++) {
            T v1 = (y[i] - x[i]) * mod1_inv_mod2 % mod2;
            if (v1 < 0) { v1 += mod2; }
            T v2 = (z[i] - (x[i] + mod1 * v1) % mod3) * mod1mod2_inv_mod3 % mod3;
            if (v2 < 0) { v2 += mod3; }
            T c = (x[i] + mod1 * v1 + mod1mod2_mod * v2) % mod;
            if (c < 0) { c += mod; }
            ans[i] = c;
        }
        return ans;
    }

private:
    static constexpr T mod1 = 167772161;
    static constexpr T mod2 = 469762049;
    static constexpr T mod3 = 1224736769;
    static constexpr T mod1_inv_mod2 = inverse(mod1, mod2);
    static constexpr T mod1mod2_inv_mod3 = inverse(mod1 * mod2, mod3);
    using NTT1 = NumberTheoreticTransformation<T, mod1, 3>;
    using NTT2 = NumberTheoreticTransformation<T, mod2, 3>;
    using NTT3 = NumberTheoreticTransformation<T, mod3, 3>;
    GarnerNumberTheoreticTransformation() = delete;
};
int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int N;
    ll P;
    std::cin >> N >> P;
    std::fill(fact, fact + 2 * MAX + 1, 1), std::fill(inv, inv + 2 * MAX + 1, 1);
    for (ll i = 2; i <= 2 * N; i++) { fact[i] = (fact[i - 1] * i) % MOD, inv[i] = ((MOD - MOD / i) * inv[MOD % i]) % MOD; }
    for (int i = 1; i <= 2 * N; i++) { (inv[i] *= inv[i - 1]) %= MOD; }
    for (int i = 0, a; i < N; i++) { std::cin >> a, R[a]++; }
    std::deque<std::vector<ll>> fs{{{1}}};
    for (int i = N - 1, k = 0; i >= 0; k += R[i], i--) {
        const int r = R[i];
        if (r == 0) { continue; }
        const ll alpha = (r * fact[r + k - 1] % MOD) * inv[k] % MOD;
        const ll beta = (k * fact[r + k - 1] % MOD) * inv[k] % MOD;
        fs.push_back({beta, alpha});
    }
    while (fs.size() > 1) {
        const auto f1 = fs.front();
        fs.pop_front();
        const auto f2 = fs.front();
        fs.pop_front();
        const auto f3 = GarnerNumberTheoreticTransformation<ll>::convolute(f1, f2, MOD);
        fs.push_back(f3);
    }
    const auto f = fs.front();
    ll ans = 0;
    for (ll i = 0, p = 1; i < f.size(); i++, (p *= P) %= MOD) { (ans += (p * i % MOD) * f[i] % MOD) %= MOD; }
    std::cout << ans << std::endl;
}

yukicoder

結果

テストケース

ソースコード