結果

問題 No.1956 猫の額
ユーザー suisensuisen
提出日時 2022-05-24 01:20:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,015 ms / 10,000 ms
コード長 4,250 bytes
コンパイル時間 1,147 ms
コンパイル使用メモリ 91,704 KB
実行使用メモリ 13,556 KB
最終ジャッジ日時 2024-09-20 14:17:15
合計ジャッジ時間 21,602 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,545 ms
13,480 KB
testcase_01 AC 38 ms
13,436 KB
testcase_02 AC 1,556 ms
13,556 KB
testcase_03 AC 56 ms
13,380 KB
testcase_04 AC 998 ms
13,484 KB
testcase_05 AC 838 ms
13,512 KB
testcase_06 AC 855 ms
13,368 KB
testcase_07 AC 109 ms
13,456 KB
testcase_08 AC 1,200 ms
13,160 KB
testcase_09 AC 117 ms
13,192 KB
testcase_10 AC 1,059 ms
13,056 KB
testcase_11 AC 499 ms
12,968 KB
testcase_12 AC 704 ms
13,184 KB
testcase_13 AC 13 ms
12,668 KB
testcase_14 AC 125 ms
12,544 KB
testcase_15 AC 42 ms
13,312 KB
testcase_16 AC 1,357 ms
13,196 KB
testcase_17 AC 2,015 ms
13,532 KB
testcase_18 AC 1,850 ms
13,320 KB
testcase_19 AC 1,520 ms
13,440 KB
testcase_20 AC 1,516 ms
13,328 KB
権限があれば一括ダウンロードができます

ソースコード

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