結果
問題 | No.2499 Sum of Products of Sums |
ユーザー |
![]() |
提出日時 | 2023-10-28 16:29:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 693 ms / 2,000 ms |
コード長 | 1,007 bytes |
コンパイル時間 | 2,003 ms |
コンパイル使用メモリ | 114,196 KB |
最終ジャッジ日時 | 2025-02-17 16:42:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <iostream> #include <atcoder/convolution> #include <atcoder/modint> using namespace std; using namespace atcoder; using mint = modint998244353; int a[1010],b[1010]; mint fa[1010]; int main(){ int i,j,h,w; cin >> h >> w; vector<mint> f = {1}; fa[0] = 1; for(i=1;i<=w;i++) fa[i] = fa[i - 1]*i; for(i=0;i<h;i++){ cin >> a[i] >> b[i]; mint val1 = w + b[i],val2 = w + a[i] - 1; mint pr1 = 1,pr2 = 1; for(j=1;j<=w;j++){ pr1 *= val1; pr1 /= j; pr2 *= val2; pr2 /= j; val1--; val2--; } vector<mint> g; g.push_back(pr1 - pr2); for(j=1;j<=w;j++){ pr1 *= val1; pr1 /= (w + j); pr2 *= val2; pr2 /= (w + j); val1--; val2--; g.push_back((pr1 - pr2)/fa[j]); } // for(mint x:g) cout << x.val() << " "; // cout << endl; f = convolution(f,g); f.resize(w + 1); } cout << (fa[w]*f[w]).val() << endl; }