結果

問題 No.1956 猫の額
ユーザー suisensuisen
提出日時 2022-05-24 01:20:58
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,220 ms / 10,000 ms
コード長 4,250 bytes
コンパイル時間 3,851 ms
コンパイル使用メモリ 125,048 KB
最終ジャッジ日時 2025-01-29 14:56:47
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

#include <atcoder/modint>
using mint = atcoder::modint;

constexpr int S = 100000;
constexpr int C = 45;

uint16_t dp[C + 1][S + 1]{};

constexpr uint16_t MOD1 = 32749;
constexpr uint16_t MOD2 = 32719;
constexpr uint16_t MOD3 = 32717;
constexpr uint16_t MOD4 = 32713;
constexpr uint16_t MOD5 = 32707;
constexpr uint16_t MOD6 = 32693;

constexpr long long M1_MOD2 = MOD1 % MOD2;
constexpr long long M1_MOD3 = MOD1 % MOD3;
constexpr long long M1_MOD4 = MOD1 % MOD4;
constexpr long long M1_MOD5 = MOD1 % MOD5;
constexpr long long M1_MOD6 = MOD1 % MOD6;
constexpr long long M1M2_MOD3 = M1_MOD3 * MOD2 % MOD3;
constexpr long long M1M2_MOD4 = M1_MOD4 * MOD2 % MOD4;
constexpr long long M1M2_MOD5 = M1_MOD5 * MOD2 % MOD5;
constexpr long long M1M2_MOD6 = M1_MOD6 * MOD2 % MOD6;
constexpr long long M1M2M3_MOD4 = M1M2_MOD4 * MOD3 % MOD4;
constexpr long long M1M2M3_MOD5 = M1M2_MOD5 * MOD3 % MOD5;
constexpr long long M1M2M3_MOD6 = M1M2_MOD6 * MOD3 % MOD6;
constexpr long long M1M2M3M4_MOD5 = M1M2M3_MOD5 * MOD4 % MOD5;
constexpr long long M1M2M3M4_MOD6 = M1M2M3_MOD6 * MOD4 % MOD6;
constexpr long long M1M2M3M4M5_MOD6 = M1M2M3M4_MOD6 * MOD5 % MOD6;
constexpr long long INV_M1_MOD2 = atcoder::internal::inv_gcd(M1_MOD2, MOD2).second;
constexpr long long INV_M1M2_MOD3 = atcoder::internal::inv_gcd(M1M2_MOD3, MOD3).second;
constexpr long long INV_M1M2M3_MOD4 = atcoder::internal::inv_gcd(M1M2M3_MOD4, MOD4).second;
constexpr long long INV_M1M2M3M4_MOD5 = atcoder::internal::inv_gcd(M1M2M3M4_MOD5, MOD5).second;
constexpr long long INV_M1M2M3M4M5_MOD6 = atcoder::internal::inv_gcd(M1M2M3M4M5_MOD6, MOD6).second;

template <uint16_t m>
std::vector<uint16_t> solve(const int c, const int s, const std::vector<int> &a) {
    for (int num = 0; num <= C; ++num) for (int sum = 0; sum <= S; ++sum) dp[num][sum] = 0;

    dp[0][0] = 1;
    for (int val : a) {
        for (int num = std::min(c, s / val); num >= 1; --num) {
            for (int sum = num * val; sum <= s; ++sum) {
                dp[num][sum] += dp[num - 1][sum - val];
                if (dp[num][sum] >= m) {
                    dp[num][sum] -= m;
                }
            }
        }
    }
    
    std::vector<uint16_t> ans(s + 1);
    std::copy(std::begin(dp[c]), std::begin(dp[c]) + s + 1, std::begin(ans));
    return ans;
}

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

    mint::set_mod(m);

    std::vector<int> a(n);
    for (auto &&e : a) std::cin >> e;
    std::sort(a.begin(), a.end(), std::greater<int>());

    const int s = std::accumulate(a.begin(), a.end(), 0);

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

    auto ans1 = solve<MOD1>(c, s, a);
    auto ans2 = solve<MOD2>(c, s, a);
    auto ans3 = solve<MOD3>(c, s, a);
    auto ans4 = solve<MOD4>(c, s, a);
    auto ans5 = solve<MOD5>(c, s, a);
    auto ans6 = solve<MOD6>(c, s, a);

    mint M1 = MOD1;
    mint M1M2 = M1 * MOD2;
    mint M1M2M3 = M1M2 * MOD3;
    mint M1M2M3M4 = M1M2M3 * MOD4;
    mint M1M2M3M4M5 = M1M2M3M4 * MOD5;

    for (int sum = 1; sum <= s; ++sum) {
        const int idx = take_compl ? s - sum : sum;
        uint16_t c1 = ans1[idx];
        uint16_t c2 = ans2[idx];
        uint16_t c3 = ans3[idx];
        uint16_t c4 = ans4[idx];
        uint16_t c5 = ans5[idx];
        uint16_t c6 = ans6[idx];

        long long x1 = c1;
        long long x2 = (atcoder::static_modint<MOD2>((long long) c2 - x1) * INV_M1_MOD2).val();
        long long x3 = (atcoder::static_modint<MOD3>((long long) c3 - x1 - x2 * M1_MOD3) * INV_M1M2_MOD3).val();
        long long x4 = (atcoder::static_modint<MOD4>((long long) c4 - x1 - x2 * M1_MOD4 - x3 * M1M2_MOD4) * INV_M1M2M3_MOD4).val();
        long long x5 = (atcoder::static_modint<MOD5>((long long) c5 - x1 - x2 * M1_MOD5 - x3 * M1M2_MOD5 - x4 * M1M2M3_MOD5) * INV_M1M2M3M4_MOD5).val();
        long long x6 = (atcoder::static_modint<MOD6>((long long) c6 - x1 - x2 * M1_MOD6 - x3 * M1M2_MOD6 - x4 * M1M2M3_MOD6 - x5 * M1M2M3M4_MOD6) * INV_M1M2M3M4M5_MOD6).val();

        mint ans = x1 + x2 * M1 + x3 * M1M2 + x4 * M1M2M3 + x5 * M1M2M3M4 + x6 * M1M2M3M4M5;

        std::cout << ans.val() << " \n"[sum == s];
    }

    return 0;
}
0