結果
問題 | No.1956 猫の額 |
ユーザー |
|
提出日時 | 2022-05-23 23:46:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 4,398 bytes |
コンパイル時間 | 2,275 ms |
コンパイル使用メモリ | 115,612 KB |
最終ジャッジ日時 | 2025-01-29 14:42:16 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 MLE * 9 |
ソースコード
#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 suisennamespace 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^24static constexpr long long MOD2 = 167772161; // 2^25static constexpr long long MOD3 = 469762049; // 2^26static 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 suisenconstexpr 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;}