結果
問題 | No.2484 Add to Variables |
ユーザー |
![]() |
提出日時 | 2023-09-22 22:07:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 2,000 ms |
コード長 | 1,864 bytes |
コンパイル時間 | 3,321 ms |
コンパイル使用メモリ | 236,916 KB |
最終ジャッジ日時 | 2025-02-17 00:41:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/convolution>using namespace std;const long long MOD = 998244353;int main(){int N, M;cin >> N >> M;vector<int> B(N);for (int i = 0; i < N; i++){cin >> B[i];}vector<int> imos(N + 1, 0);int D = 0;for (int i = 0; i < N - 1; i++){if (B[i] < B[i + 1]){D += B[i + 1] - B[i];imos[i + 1] += B[i + 1] - B[i];imos[N] -= B[i + 1] - B[i];} else {D += B[i] - B[i + 1];imos[0] += B[i] - B[i + 1];imos[i + 1] -= B[i] - B[i - 1];}}for (int i = 0; i < N; i++){imos[i + 1] += imos[i];}if (D > M || imos[0] > B[0]){cout << 0 << endl;} else {int a = M - D;int b = B[0] - imos[0];if (b > a){cout << 0 << endl;} else {vector<long long> inv(M + 1);inv[1] = 1;for (int i = 2; i <= M; i++){inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;}vector<long long> fact(M + 1);vector<long long> finv(M + 1);fact[0] = 1;finv[0] = 1;for (int i = 1; i <= M; i++){fact[i] = fact[i - 1] * i % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}vector<vector<long long>> f(3, vector<long long>(M + 1, 0));for (int i = 0; i < 3; i++){int d = abs(B[i] - B[i + 1]);for (int j = 0; j <= M - d; j++){f[i][j] = finv[j] * finv[d + j] % MOD;}}vector<long long> P(M + 1, 0);P[0] = 1;for (int i = 0; i < 3; i++){P = atcoder::convolution(P, f[i]);P.resize(M + 1);}long long ans = 0;for (int i = 0; i <= M; i++){if (a >= i * 2 && b >= i && a - i * 2 >= b - i){ans += P[i] * finv[b - i] % MOD * finv[a - b - i] % MOD * fact[M] % MOD;}}ans %= MOD;cout << ans << endl;}}}