Submission #64315168

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
using namespace std;
 
using ll = long long;
const ll MOD = 998244353;
 
// 繰り返し二乗法による高速な mod 累乗
ll modexp(ll a, ll b, ll mod=MOD) {
    ll res = 1 % mod;
    a %= mod;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
 
int main(){
    ios::sync_with_stdio(false);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
using namespace std;
 
using ll = long long;
const ll MOD = 998244353;
 
// 繰り返し二乗法による高速な mod 累乗
ll modexp(ll a, ll b, ll mod=MOD) {
    ll res = 1 % mod;
    a %= mod;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }
    
    // P[i] = A[0] + A[1] + ... + A[i-1] (P[0]=0)
    vector<ll> P(N+1, 0);
    for (int i = 0; i < N; i++){
        P[i+1] = P[i] + A[i];
    }
    
    // powP[m][i] = (P[i])^m mod MOD を precompute
    // m=0～K, i=0～N
    vector<vector<ll>> powP(K+1, vector<ll>(N+1, 0));
    for (int i = 0; i <= N; i++){
        powP[0][i] = 1; // 定義より P[i]^0 = 1
    }
    for (int m = 1; m <= K; m++){
        for (int i = 0; i <= N; i++){
            ll x = P[i] % MOD;
            powP[m][i] = (powP[m-1][i] * x) % MOD;
        }
    }
    
    // 累積和 cum[m][j] = sum_{i=0}^{j-1} powP[m][i] を precompute
    //  j = 1,...,N+1 としておく（cum[m][0] = 0）
    vector<vector<ll>> cum(K+1, vector<ll>(N+2, 0));
    for (int m = 0; m <= K; m++){
        cum[m][0] = 0;
        for (int j = 1; j <= N+1; j++){
            cum[m][j] = (cum[m][j-1] + powP[m][j-1]) % MOD;
        }
    }
    
    // (P[j]-P[i])^K を二項展開すると、
    //   (P[j]-P[i])^K = sum_{m=0}^{K} (-1)^m * binom(K, m) * P[j]^(K-m) * P[i]^m
    // よって全体の和は
    //   ans = sum_{m=0}^{K} (-1)^m * binom(K, m) * sum_{j=1}^{N} [ P[j]^(K-m) * (sum_{i=0}^{j-1} P[i]^m ) ]
    // として計算可能．
    
    // binom[m] = binom(K, m) を計算 (K ≤ 10 なので簡単な方法で)
    vector<ll> binom(K+1, 0);
    binom[0] = 1;
    for (int m = 1; m <= K; m++){
        binom[m] = (binom[m-1] * (K - m + 1)) % MOD;
        ll inv = modexp(m, MOD-2, MOD);
        binom[m] = (binom[m] * inv) % MOD;
    }
    
    ll ans = 0;
    // m = 0 ... K について和をとる
    for (int m = 0; m <= K; m++){
        // (-1)^m * binom(K, m)
        ll coeff = (m % 2 == 0 ? binom[m] : (MOD - binom[m]) % MOD);
        ll sum_j = 0;
        // j = 1 ... N について
        // P[j]^(K-m) は powP[K-m][j]，また i の和は cum[m][j] により求められる
        for (int j = 1; j <= N; j++){
            sum_j = (sum_j + (powP[K-m][j] * cum[m][j]) % MOD) % MOD;
        }
        ans = (ans + coeff * sum_j) % MOD;
    }
    cout << ans % MOD << "\n";
    return 0;
}

Submission Info

Judge Result