結果
問題 | No.2499 Sum of Products of Sums |
ユーザー |
|
提出日時 | 2023-09-04 13:51:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,000 ms |
コード長 | 1,180 bytes |
コンパイル時間 | 4,427 ms |
コンパイル使用メモリ | 259,836 KB |
最終ジャッジ日時 | 2025-02-16 18:34:48 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; struct Fast { Fast() { std::cin.tie(nullptr); ios::sync_with_stdio(false); cout << setprecision(10); } } fast; #define rep(i, a, b) for (int(i) = (int)(a); (i) < (int)(b); (i)++) #define rrep(i, a, b) for (int(i) = (int)(b)-1; (i) >= (int)(a); (i)--) using ll = long long; using mint = modint998244353; int main() { int h, w; cin >> h >> w; int factsz = 2 * w + 1; vector<mint> fact(factsz), ifact(factsz); fact[0] = 1; rep(i, 1, factsz) fact[i] = fact[i - 1] * i; ifact[factsz - 1] = fact[factsz - 1].inv(); rrep(i, 1, factsz) ifact[i - 1] = ifact[i] * i; vector<mint> f(w + 1, 0); f[0] = fact[w]; rep(i, 0, h) { ll a, b; cin >> a >> b; vector<mint> g(w + 1); mint fallfact_a = 1, fallfact_b = 1; rep(i, 0, w) { fallfact_a *= w + a - 1 - i; fallfact_b *= w + b - i; } rep(i, 0, w + 1) { g[i] = (fallfact_b - fallfact_a) * ifact[i] * ifact[i + w]; fallfact_a *= a - 1 - i; fallfact_b *= b - i; } f = convolution(f, g); f.resize(w + 1); } cout << f[w].val() << endl; }