結果
問題 | 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;}