結果

問題 No.829 成長関数インフレ中
ユーザー PachicobuePachicobue
提出日時 2018-12-06 17:43:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,790 bytes
コンパイル時間 1,721 ms
コンパイル使用メモリ 100,104 KB
実行使用メモリ 23,680 KB
最終ジャッジ日時 2024-09-15 13:18:18
合計ジャッジ時間 10,519 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
15,104 KB
testcase_01 AC 5 ms
9,560 KB
testcase_02 AC 4 ms
9,728 KB
testcase_03 AC 5 ms
9,600 KB
testcase_04 AC 5 ms
9,568 KB
testcase_05 AC 4 ms
9,564 KB
testcase_06 AC 5 ms
9,668 KB
testcase_07 AC 5 ms
9,696 KB
testcase_08 AC 5 ms
9,564 KB
testcase_09 AC 4 ms
9,600 KB
testcase_10 AC 5 ms
9,600 KB
testcase_11 AC 4 ms
9,856 KB
testcase_12 AC 29 ms
9,672 KB
testcase_13 AC 6 ms
9,728 KB
testcase_14 AC 20 ms
9,600 KB
testcase_15 AC 744 ms
13,240 KB
testcase_16 AC 1,532 ms
16,856 KB
testcase_17 TLE -
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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