結果
問題 |
No.2499 Sum of Products of Sums
|
ユーザー |
![]() |
提出日時 | 2024-03-10 20:27:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 370 ms / 2,000 ms |
コード長 | 1,281 bytes |
コンパイル時間 | 2,529 ms |
コンパイル使用メモリ | 142,580 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-29 21:46:26 |
合計ジャッジ時間 | 4,714 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <iostream> #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) #include <atcoder/modint> #include <atcoder/convolution> using mint = atcoder::modint998244353; // [x^B] 1/(m!) * (x / (1 - x)^2 )^m (1 / (1 - x))^(W - m + 1) を m = 0, ..., W で列挙 // [x^B] 1/m! * x^m / (1 - x)^(W + 1 + m) // 1/m! [x^(B - m)] 1 / (1 - x)^(W + 1 + m) // 1/m! Comb(B + W, W + m) vector<mint> gen(int W, int B) { vector<mint> ret(W + 1); mint num = 1, den = 1; REP(_, W) { num *= B + W - _; den *= W - _; } ret.at(0) = num / den; FOR(m, 1, W + 1) { num *= B + W - W + 1 - m; den *= W + m; den *= m; ret.at(m) = num / den; } return ret; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int H, W; cin >> H >> W; vector<mint> dp{1}; for (int i = 0; i < H; ++i) { int a, b; cin >> a >> b; auto f = gen(W, b); auto g = gen(W, a - 1); REP(i, g.size()) f.at(i) -= g.at(i); dp = atcoder::convolution(dp, f); dp.resize(W + 1); } mint ret = dp.back(); FOR(i, 1, W + 1) ret *= i; cout << ret.val() << '\n'; }