Submission #64331788

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5, mod = 998244353;
int n, k;
int a[MAXN + 5];
int sum[MAXN + 5];
int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b &1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int C[15 + 5][15 + 5];
int ss[15];
signed main() {
    for (int i = 0; i <= 13; i ++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j ++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    cin >> n >> k;
    for (int i= 1; i <= n; i ++) {
        cin >> a[i];
           sum[i] = (sum[i - 1] + a[i]) % mod;
    }
    int ans = 0;
	ss[0] = 1;
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= k; j ++) {
            (ans += C[k][j] * qpow(sum[i], j) % mod * ss[k - j]%mod) %= mod;
        }
		ans = (ans % mod + mod) % mod;
        for (int j = 0; j <= k; j ++) {
            (ss[j] += qpow(-sum[i], j)) %= mod;
        }
    }
    cout<<ans;
    return 0;
}

Submission Info

Submission Time
Task F - Range Power Sum
User laozhuma
Language C++ 20 (gcc 12.2)
Score 550
Code Size 1046 Byte
Status AC
Exec Time 80 ms
Memory 6804 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 550 / 550
Status
AC × 3
AC × 44
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 02_random2_00.txt, 02_random2_01.txt, 02_random2_02.txt, 03_minmax_00.txt, 03_minmax_01.txt, 03_minmax_02.txt, 03_minmax_03.txt, 03_minmax_04.txt, 03_minmax_05.txt, 03_minmax_06.txt, 03_minmax_07.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3560 KiB
00_sample_01.txt AC 1 ms 3652 KiB
00_sample_02.txt AC 1 ms 3532 KiB
01_random_00.txt AC 3 ms 3812 KiB
01_random_01.txt AC 52 ms 6684 KiB
01_random_02.txt AC 51 ms 6804 KiB
01_random_03.txt AC 40 ms 5752 KiB
01_random_04.txt AC 54 ms 6576 KiB
01_random_05.txt AC 54 ms 6624 KiB
01_random_06.txt AC 39 ms 5640 KiB
01_random_07.txt AC 56 ms 6588 KiB
01_random_08.txt AC 57 ms 6552 KiB
01_random_09.txt AC 40 ms 5600 KiB
01_random_10.txt AC 60 ms 6580 KiB
01_random_11.txt AC 59 ms 6652 KiB
01_random_12.txt AC 8 ms 3880 KiB
01_random_13.txt AC 62 ms 6664 KiB
01_random_14.txt AC 62 ms 6552 KiB
01_random_15.txt AC 31 ms 5036 KiB
01_random_16.txt AC 65 ms 6680 KiB
01_random_17.txt AC 65 ms 6604 KiB
01_random_18.txt AC 39 ms 5232 KiB
01_random_19.txt AC 69 ms 6768 KiB
01_random_20.txt AC 68 ms 6768 KiB
01_random_21.txt AC 36 ms 5096 KiB
01_random_22.txt AC 72 ms 6604 KiB
01_random_23.txt AC 72 ms 6616 KiB
01_random_24.txt AC 7 ms 3964 KiB
01_random_25.txt AC 76 ms 6740 KiB
01_random_26.txt AC 76 ms 6664 KiB
01_random_27.txt AC 55 ms 5668 KiB
01_random_28.txt AC 80 ms 6744 KiB
01_random_29.txt AC 80 ms 6576 KiB
02_random2_00.txt AC 79 ms 6616 KiB
02_random2_01.txt AC 80 ms 6620 KiB
02_random2_02.txt AC 79 ms 6680 KiB
03_minmax_00.txt AC 1 ms 3484 KiB
03_minmax_01.txt AC 1 ms 3436 KiB
03_minmax_02.txt AC 1 ms 3500 KiB
03_minmax_03.txt AC 1 ms 3684 KiB
03_minmax_04.txt AC 21 ms 6772 KiB
03_minmax_05.txt AC 53 ms 6604 KiB
03_minmax_06.txt AC 48 ms 6556 KiB
03_minmax_07.txt AC 80 ms 6580 KiB