結果
問題 | No.2484 Add to Variables |
ユーザー |
|
提出日時 | 2023-09-22 22:28:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 2,266 bytes |
コンパイル時間 | 4,318 ms |
コンパイル使用メモリ | 259,764 KB |
最終ジャッジ日時 | 2025-02-17 00:50:57 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 |
ソースコード
#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 all(a) (a).begin(), (a).end()#define contains(a, x) ((a).find(x) != (a).end())#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)#define writejoin(s, a) rep(_i, 0, (a).size()) cout << (a)[_i] << (_i + 1 < (int)(a).size() ? s : "\n");#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";#define yn(b) cout << ((b) ? "yes" : "no") << "\n";template <typename mint>class Factorial {public:Factorial(int max) : n(max) {f = vector<mint>(n + 1);finv = vector<mint>(n + 1);f[0] = 1;for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i;finv[n] = f[n].inv();for (int i = n; i > 0; i--) finv[i - 1] = finv[i] * i;}mint fact(int k) {assert(0 <= k && k <= n);return f[k];}mint fact_inv(int k) {assert(0 <= k && k <= n);return finv[k];}mint binom(int k, int r) {assert(0 <= k && k <= n);if (r < 0 || r > k) return 0;return f[k] * finv[r] * finv[k - r];}mint inv(int k) {assert(0 < k && k <= n);return finv[k] * f[k - 1];}private:int n;vector<mint> f, finv;};using ll = long long;using vi = vector<int>;using vvi = vector<vi>;using vl = vector<ll>;using mint = modint998244353;int main() {int n, m;cin >> n >> m;vi b(n);rep(i, 0, n) cin >> b[i];rrep(i, 1, n) b[i] -= b[i - 1];int sum = 0;rep(i, 0, n) sum += b[i];if (sum > m) {cout << 0 << "\n";} else {b[0] -= m - sum;int sumabs = 0;rep(i, 0, n) sumabs += abs(b[i]);if (sumabs > m) {cout << 0 << "\n";} else {Factorial<mint> fact(1000000);vector<mint> f{fact.fact(m)};rep(i, 0, n) {int v = abs(b[i]);vector<mint> g(m + 1, 0);for (int j = 0; v + 2 * j <= m; j++)g[v + 2 * j] = fact.fact_inv(j) * fact.fact_inv(v + j);f = convolution(f, g);f.resize(m + 1);}cout << f[m].val() << "\n";}}}