結果

問題 No.1956 猫の額
ユーザー suisensuisen
提出日時 2022-05-23 23:46:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 4,398 bytes
コンパイル時間 2,280 ms
コンパイル使用メモリ 118,568 KB
実行使用メモリ 22,096 KB
最終ジャッジ日時 2023-10-20 18:38:28
合計ジャッジ時間 31,445 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 AC 72 ms
5,992 KB
testcase_02 MLE -
testcase_03 AC 128 ms
6,784 KB
testcase_04 AC 2,920 ms
14,440 KB
testcase_05 AC 2,043 ms
13,648 KB
testcase_06 AC 2,191 ms
12,856 KB
testcase_07 AC 394 ms
5,728 KB
testcase_08 MLE -
testcase_09 AC 70 ms
8,632 KB
testcase_10 MLE -
testcase_11 AC 244 ms
11,008 KB
testcase_12 AC 340 ms
11,800 KB
testcase_13 AC 5 ms
4,348 KB
testcase_14 AC 55 ms
4,936 KB
testcase_15 AC 29 ms
6,256 KB
testcase_16 MLE -
testcase_17 MLE -
testcase_18 MLE -
testcase_19 MLE -
testcase_20 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <array>
#include <iostream>
#include <vector>

#include <atcoder/modint>

using mint = atcoder::modint;

#include <atcoder/convolution>
#include <iostream>

#include <vector>

namespace suisen::internal {
    template <typename T>
    std::vector<T> convolution_naive(const std::vector<T>& a, const std::vector<T>& b) {
        const int n = a.size(), m = b.size();
        std::vector<T> c(n + m - 1);
        if (n < m) {
            for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) c[i + j] += a[i] * b[j];
        } else {
            for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) c[i + j] += a[i] * b[j];
        }
        return c;
    }
} // namespace suisen

namespace suisen {
    template <typename mint, atcoder::internal::is_modint_t<mint>* = nullptr>
    std::vector<mint> arbitrary_mod_convolution(const std::vector<mint>& a, const std::vector<mint>& b) {
        int n = int(a.size()), m = int(b.size());
        if (n == 0 or m == 0) return {};
        if (std::min(n, m) <= 60) return internal::convolution_naive(a, b);

        static constexpr long long MOD1 = 754974721;  // 2^24
        static constexpr long long MOD2 = 167772161;  // 2^25
        static constexpr long long MOD3 = 469762049;  // 2^26
        static constexpr long long M1M2 = MOD1 * MOD2;
        static constexpr long long INV_M1_MOD2 = atcoder::internal::inv_gcd(MOD1, MOD2).second;
        static constexpr long long INV_M1M2_MOD3 = atcoder::internal::inv_gcd(M1M2, MOD3).second;

        std::vector<int> a2(n), b2(m);
        for (int i = 0; i < n; ++i) a2[i] = a[i].val();
        for (int i = 0; i < m; ++i) b2[i] = b[i].val();

        auto c1 = atcoder::convolution<MOD1>(a2, b2);
        auto c2 = atcoder::convolution<MOD2>(a2, b2);
        auto c3 = atcoder::convolution<MOD3>(a2, b2);

        const long long m1m2 = mint(M1M2).val();
        std::vector<mint> c(n + m - 1);
        for (int i = 0; i < n + m - 1; ++i) {
            // Garner's Algorithm
            // X = x1 + x2 * m1 + x3 * m1 * m2
            // x1 = c1[i], x2 = (c2[i] - x1) / m1 (mod m2), x3 = (c3[i] - x1 - x2 * m1) / m2 (mod m3)
            long long x1 = c1[i];
            long long x2 = (atcoder::static_modint<MOD2>(c2[i] - x1) * INV_M1_MOD2).val();
            long long x3 = (atcoder::static_modint<MOD3>(c3[i] - x1 - x2 * MOD1) * INV_M1M2_MOD3).val();
            c[i] = x1 + x2 * MOD1 + x3 * m1m2;
        }
        return c;
    }
} // namespace suisen

constexpr int N = 100000;

int main() {
    int n, m, c;
    std::cin >> n >> m >> c;
    mint::set_mod(m);

    std::vector<std::vector<mint>> binom(n + 1, std::vector<mint>(n + 1));
    binom[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        binom[i][0] = binom[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }

    int s = 0;
    std::array<int, N + 1> cnt{};
    for (int i = 0; i < n; ++i) {
        int e;
        std::cin >> e;
        s += e;
        ++cnt[e];
    }

    bool take_compl = 2 * c >= n;
    if (take_compl) {
        c = n - c;
    }

    std::vector dp(c + 1, std::vector<mint>(s + 1));
    dp[0][0] = 1;
    for (int val = N; val >= 1; --val) {
        const int p = cnt[val];
        if (p == 0) continue;

        std::vector<mint> g(p + 1);
        for (int i = 0; i <= p; ++i) {
            g[i] = binom[p][i];
        }

        for (int sum_mod = 0; sum_mod < val; ++sum_mod) {
            const int max_diff = (s - sum_mod) / val;
            for (int diff = 0; diff <= max_diff; ++diff) {
                const int max_num = std::min(c, (s - sum_mod) / val - diff);
                std::vector<mint> f(max_num + 1);
                for (int num = 0; num <= max_num; ++num) {
                    f[num] = dp[num][(num + diff) * val + sum_mod];
                }
                std::vector<mint> h = suisen::arbitrary_mod_convolution(f, g);
                for (int num = 0; num <= max_num; ++num) {
                    dp[num][(num + diff) * val + sum_mod] = h[num];
                }
            }
        }
    }

    if (take_compl) {
        for (int sum = 1; sum <= s; ++sum) {
            std::cout << dp[c][s - sum].val() << " \n"[sum == s];
        }
    } else {
        for (int sum = 1; sum <= s; ++sum) {
            std::cout << dp[c][sum].val() << " \n"[sum == s];
        }
    }

    return 0;
}
0