結果

問題 No.1956 猫の額
ユーザー suisensuisen
提出日時 2022-05-24 01:20:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,101 ms / 10,000 ms
コード長 4,250 bytes
コンパイル時間 1,216 ms
コンパイル使用メモリ 91,056 KB
実行使用メモリ 13,612 KB
最終ジャッジ日時 2023-10-20 18:41:27
合計ジャッジ時間 22,245 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,571 ms
13,612 KB
testcase_01 AC 33 ms
13,612 KB
testcase_02 AC 1,597 ms
13,612 KB
testcase_03 AC 56 ms
13,612 KB
testcase_04 AC 1,012 ms
13,612 KB
testcase_05 AC 842 ms
13,612 KB
testcase_06 AC 893 ms
13,612 KB
testcase_07 AC 111 ms
13,612 KB
testcase_08 AC 1,247 ms
13,348 KB
testcase_09 AC 117 ms
13,348 KB
testcase_10 AC 1,094 ms
13,140 KB
testcase_11 AC 509 ms
13,216 KB
testcase_12 AC 726 ms
13,344 KB
testcase_13 AC 9 ms
12,908 KB
testcase_14 AC 131 ms
12,792 KB
testcase_15 AC 40 ms
13,396 KB
testcase_16 AC 1,444 ms
13,348 KB
testcase_17 AC 2,101 ms
13,612 KB
testcase_18 AC 1,890 ms
13,612 KB
testcase_19 AC 1,609 ms
13,612 KB
testcase_20 AC 1,583 ms
13,612 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