結果

問題 No.2717 Sum of Subarray of Subsequence
ユーザー startcpp
提出日時 2024-04-05 22:15:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 1,466 bytes
コンパイル時間 819 ms
コンパイル使用メモリ 78,984 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 02:29:32
合計ジャッジ時間 2,901 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <algorithm>
#include <vector>
#include <atcoder/modint>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
using namespace atcoder;
using mint = modint998244353;
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
void experiment() {
    int n, i, j, k, l;
    int mats[16][16];
    int cnts[16];
    for (n = 1; n <= 15; n++) {
        vector<int> kiyo(n);
        int cnt = 0;
        for (i = 1; i < (1 << n); i++) {
            vector<int> vec;
            rep(j, n) if ((i >> j) % 2) vec.push_back(j);
            rep(j, vec.size()) {
                for (k = j; k < vec.size(); k++) {
                    cnt++;
                    for (l = j; l <= k; l++) kiyo[vec[l]]++;
                }
            }
        }
        rep(i, n) mats[n][i] = kiyo[i];
        cnts[n] = cnt;
    }
    for (n = 2; n <= 15; n++) {
        rep(i, n - 1) {
            int si = mats[n][i];
            int bo = mats[n - 1][i];
            int g = gcd(si, bo);
            si /= g; bo /= g;
            printf("%5lld/%5lld ", si, bo);
        }
        cout << endl;
    }
}
//長さiのときの先頭要素の寄与a[i]を求める
vector<mint> make_seqs(int n) {
    int i;
    vector<mint> a(n);
    a[1] = 1;
    for (i = 2; i < n; i++) {
        if (i % 2 == 0) {
            a[i] = a[i - 1] * mint(i + 1) / mint(i / 2);    
        }
        else {
            a[i] = a[i - 1] * mint(2 * i + 2) / mint(i);
        }
    }
    return a;
}
signed main() {
    int n, i;
    cin >> n;
    vector<mint> pekora = make_seqs(n + 1);
    mint ans = 0;
    rep(i, n) {
        int x; cin >> x;
        ans += mint(x) * pekora[i + 1] * pekora[n - i];
    }
    cout << ans.val() << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0