結果
問題 |
No.2164 Equal Balls
|
ユーザー |
|
提出日時 | 2022-12-24 02:47:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 431 ms / 5,000 ms |
コード長 | 1,543 bytes |
コンパイル時間 | 2,581 ms |
コンパイル使用メモリ | 121,864 KB |
最終ジャッジ日時 | 2025-02-09 19:54:13 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <iostream> #include <deque> #include <vector> #include <atcoder/modint> #include <atcoder/convolution> using mint = atcoder::modint998244353; constexpr int L = 300; constexpr int M = 2 * L + 1; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> a(n), b(n); for (auto &&e : a) std::cin >> e; for (auto &&e : b) std::cin >> e; std::vector binom(M, std::vector<mint>(M)); for (int i = 0; i < M; ++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]; } } std::deque<std::vector<mint>> fs; for (int i = 0; i < m; ++i) { int miny = L; std::vector<int> x, y; for (int j = i; j < n; j += m) { x.push_back(a[j]); y.push_back(b[j]); miny = std::min(miny, b[j]); } const int siz = x.size(); std::vector<mint> f(M, 0); std::fill(f.begin() + (L - miny), f.end(), 1); for (int j = 0; j < siz; ++j) { for (int d = -miny; d <= L; ++d) { f[L + d] *= binom[x[j] + y[j]][d + y[j]]; } } fs.emplace_back(std::move(f)); } while (fs.size() >= 2) { auto f = fs.front(); fs.pop_front(); auto g = fs.front(); fs.pop_front(); fs.push_back(atcoder::convolution(f, g)); } std::cout << fs.front()[m * L].val() << std::endl; }