結果
問題 | No.2717 Sum of Subarray of Subsequence |
ユーザー |
![]() |
提出日時 | 2024-04-05 22:38:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 3,381 bytes |
コンパイル時間 | 2,352 ms |
コンパイル使用メモリ | 197,336 KB |
最終ジャッジ日時 | 2025-02-20 21:50:38 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 1e9 + 10;const ll INFL = 4e18;template <ll MOD>struct modint {ll value;modint(ll x = 0) {if (x >= 0) {value = x % MOD;} else {value = MOD - (-x) % MOD;}}modint operator-() const {return modint(-value);}modint operator+() const {return modint(*this);}modint &operator+=(const modint &other) {value += other.value;if (value >= MOD) {value -= MOD;}return *this;}modint &operator-=(const modint &other) {value += MOD - other.value;if (value >= MOD) {value -= MOD;}return *this;}modint &operator*=(const modint other) {value = value * other.value % MOD;return *this;}modint &operator/=(modint other) {(*this) *= other.inv();return *this;}modint operator+(const modint &other) const {return modint(*this) += other;}modint operator-(const modint &other) const {return modint(*this) -= other;}modint operator*(const modint &other) const {return modint(*this) *= other;}modint operator/(const modint &other) const {return modint(*this) /= other;}modint pow(ll x) const {modint ret(1), mul(value);while (x) {if (x & 1) {ret *= mul;}mul *= mul;x >>= 1;}return ret;}modint inv() const {return pow(MOD - 2);}bool operator==(const modint &other) const {return value == other.value;}bool operator!=(const modint &other) const {return value != other.value;}friend ostream &operator<<(ostream &os, const modint &x) {return os << x.value;}friend istream &operator>>(istream &is, modint &x) {ll v;is >> v;x = modint<MOD>(v);return is;}};using mod998 = modint<998244353>;using mod107 = modint<1000000007>;template <typename T>struct combination {vector<T> fact, factinv;combination(int n) {fact = vector<T>(n + 1);factinv = vector<T>(n + 1);fact[0] = 1;for (int i = 1; i <= n; i++) {fact[i] = fact[i - 1] * i;}for (int i = 0; i <= n; i++) {factinv[i] = fact[i].inv();}}T nCr(ll n, ll r) {if (n < 0 || r < 0 || n - r < 0) {return 0;}return fact[n] * factinv[r] * factinv[n - r];}T nPr(ll n, ll r) {if (n < 0 || r < 0 || n - r < 0) {return 0;}return fact[n] * factinv[n - r];}};using mint = mod998;int main() {int N;cin >> N;vector<mint> A(N);for (int i = 0; i < N; i++) {cin >> A[i];}combination<mint> C(N);auto F = [&](int n) {if (n == 0) {return mint(1);}return mint(2).pow(n - 1) * (n + 2);};vector<mint> cnt(N);for (int i = 0; i < N; i++) {cnt[i] = F(N - i - 1) * F(i);}mint ans = 0;for (int i = 0; i < N; i++) {ans += cnt[i] * A[i];}cout << ans << endl;}