結果
問題 |
No.2485 Add to Variables (Another)
|
ユーザー |
|
提出日時 | 2024-03-04 23:30:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 175 ms / 2,000 ms |
コード長 | 1,155 bytes |
コンパイル時間 | 4,780 ms |
コンパイル使用メモリ | 259,776 KB |
最終ジャッジ日時 | 2025-02-20 00:52:15 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 39 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using mint = modint998244353; mint fac[200000], facinv[200000]; void init(){ fac[0] = 1; for(int i = 1; i < 200000; i++) fac[i] = fac[i - 1] * i; facinv[200000 - 1] = 1 / fac[200000 - 1]; for(int i = 200000 - 2; i >= 0; i--) facinv[i] = facinv[i + 1] * (i + 1); } int main(){ init(); int n, m; cin >> n >> m; vector<int> b(n); for(int i = 0; i < n; i++) cin >> b[i]; if(n == 1){ cout << (fac[m] * facinv[m - b[0]] * facinv[b[0]]).val() << endl; return 0; } vector<int> a(n - 1); for(int i = 0; i < n - 1; i++) a[i] = b[i + 1] - b[i]; vector<mint> ret(1, 1); for(int i = 0; i < n - 1; i++){ vector<mint> v(m + 1); for(int j = 0; j <= m; j++){ if(a[i] + j < 0 || a[i] + 2 * j > m) continue; v[a[i] + 2 * j] = facinv[j] * facinv[a[i] + j]; } ret = convolution(ret, v); ret.resize(m + 1); } int x = b[0] + b[n - 1]; mint ans = 0; for(int i = 0; i * 2 <= x; i++){ mint c = ret[x - 2 * i] * facinv[i] * facinv[m - x + i]; ans += c; } ans *= fac[m]; cout << ans.val() << endl; }