結果

問題 No.3328 岩井ツリーグラフ
コンテスト
ユーザー bolero
提出日時 2025-10-19 16:50:25
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 259 ms / 2,000 ms
コード長 1,345 bytes
コンパイル時間 6,554 ms
コンパイル使用メモリ 334,932 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-19 16:50:37
合計ジャッジ時間 10,922 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main()
{
    long long X;
    cin >> X;
    vector<atcoder::modint998244353> Y(X);
    rep(i, X)
    {
        long long y;
        cin >> y;
        Y[i] = y;
    }

    atcoder::modint998244353 sum_dist_from_0 = 0;
    atcoder::modint998244353 v_cnt = 1;

    // 項数n,初項a0,公差dのときの総和
    auto f = [&](atcoder::modint998244353 n, atcoder::modint998244353 a0, atcoder::modint998244353 d) -> atcoder::modint998244353
    {
        return n * (2 * a0 + (n - 1) * d) / 2;
    };

    auto f2 = [&](atcoder::modint998244353 n) -> atcoder::modint998244353
    {
        return n * (n + 1) * (2 * n + 1) / 6;
    };

    atcoder::modint998244353 ans = 0;
    for (auto y : Y)
    {
        /*
        atcoder::modint998244353 val = sum_dist_from_0;
        rep(i, y.val())
        {
            val += v_cnt + i;
            ans += val;
        }
        */

        atcoder::modint998244353 val1 = sum_dist_from_0 * y;
        atcoder::modint998244353 val2 = f(y, 1, 1) * v_cnt;
        atcoder::modint998244353 val3 = (f2(y) - f(y, 1, 1)) / 2;

        ans += val1 + val2 + val3;

        sum_dist_from_0 += y * (y + 1) / 2;
        v_cnt += y;
    }

    cout << ans.val() << endl;

    return 0;
}
0