結果

問題 No.1956 猫の額
ユーザー hitonanode
提出日時 2022-05-23 21:55:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 737 ms / 10,000 ms
コード長 3,020 bytes
コンパイル時間 1,692 ms
コンパイル使用メモリ 127,884 KB
実行使用メモリ 13,364 KB
最終ジャッジ日時 2024-09-20 14:03:54
合計ジャッジ時間 11,651 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

// C ではなく min(C, N - C) にして半分
// short int を使って更に半分（？）
// -> DP テーブルが 9MB くらい...
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cassert>
#include <numeric>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

// Require: 1 <= b
// return: (g, x) s.t. g = gcd(a, b), xa = g MOD b, 0 <= x < b/g
template <class Int> /* constexpr */ std::pair<Int, Int> inv_gcd(Int a, Int b) {
    a %= b;
    if (a < 0) a += b;
    if (a == 0) return {b, 0};
    Int s = b, t = a, m0 = 0, m1 = 1;
    while (t) {
        Int u = s / t;
        s -= t * u, m0 -= m1 * u;
        auto tmp = s;
        s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

template <class Int>
/* constexpr */ std::pair<Int, Int> crt(const std::vector<Int> &r, const std::vector<Int> &m) {
    assert(r.size() == m.size());
    int n = int(r.size());
    // Contracts: 0 <= r0 < m0
    Int r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        assert(1 <= m[i]);
        Int r1 = r[i] % m[i], m1 = m[i];
        if (r1 < 0) r1 += m1;
        if (m0 < m1) {
            std::swap(r0, r1);
            std::swap(m0, m1);
        }
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }
        Int g, im;
        std::tie(g, im) = inv_gcd<Int>(m0, m1);

        Int u1 = m1 / g;
        if ((r1 - r0) % g) return {0, 0};

        Int x = (r1 - r0) / g % u1 * im % u1;
        r0 += x * m0;
        m0 *= u1;
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}

vector<unsigned short> solve_md(const vector<int> &A, int hi, int C, unsigned short md) {
    vector dp(C + 1, vector<unsigned short>(hi + 1));
    dp[C][0] = 1;
    for (auto a : A) {
        REP(c, C) {
            REP(i, hi - a + 1) {
                dp[c][i + a] += dp[c + 1][i];
                if (dp[c][i + a] < dp[c + 1][i] or dp[c][i + a] >= md) dp[c][i + a] -= md;
            }
        }
    }
    return dp.front();
}


int main() {
    const vector<__int128> mods{65521, 65519, 65497, 65479, 65449, 65447};
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, M, C;
    cin >> N >> M >> C;
    vector<int> A(N);
    for (auto &x : A) cin >> x;

    const int maxi = accumulate(A.begin(), A.end(), 0);
    const int c_use = min(C, N - C);

    vector<vector<unsigned short>> answers;
    for (unsigned short md : mods) {
        auto sol = solve_md(A, maxi, c_use, md);
        answers.push_back(sol);
    }

    vector<int> ret(maxi + 1);
    REP(i, ret.size()) {
        vector<__int128> B;
        REP(d, mods.size()) B.push_back(answers[d][i]);
        ret[i] = crt(B, mods).first % M;
    }

    if (C != c_use) reverse(ret.begin(), ret.end());
    ret.erase(ret.begin());
    for (auto x : ret) cout << x << ' ';
    cout << '\n';
}
0