結果
問題 |
No.2754 Cumulate and Drop
|
ユーザー |
|
提出日時 | 2024-05-11 17:51:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 1,499 bytes |
コンパイル時間 | 1,845 ms |
コンパイル使用メモリ | 198,740 KB |
最終ジャッジ日時 | 2025-02-21 13:41:57 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using Matrix = vector<vector<ll>>; const int inf = 1000000000; const ll INF = 1000000000000000000; const ll mod = 998244353; const ull mod_hash = (1UL << 61) - 1; const vector<int> dx = {0, 1, 0, -1, 1, 1, -1, -1}; const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1}; struct BinomialCoefficient { int N = 1010000; //maxN ll m; //prime vector<ll> fac, finv, inv; BinomialCoefficient(ll m) : m(m), fac(N, 1), finv(N, 1), inv(N, 1) { for (int i = 2; i < N; i++) { fac[i] = (fac[i - 1] * i) % m; inv[i] = (m - (inv[m % i] * (m / i)) % m); finv[i] = (finv[i - 1] * inv[i]) % m; } } ll C(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % m) % m; } ll P(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * finv[n - k] % m; } }; ll extGCD(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll d = extGCD(b, a % b, x, y); swap(x, y); y -= a / b * x; return d; } int main(){ int N;cin>>N; vector<ll> A(N); for (int i = 0; i < N; i++) cin>>A[i]; BinomialCoefficient com(mod); ll ans = 0; for (int i = 0; i < N; i++) { ans += (((com.C(N - 1 + N - i - 1, N - 1) - com.C(N - 1 + N - i - 1, N - 1 - 1 - i)) % mod) + mod) % mod * A[i] % mod; ans %= mod; } cout << ans << endl; return 0; }