Submission #64269896

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using mint = atcoder::modint998244353;
#define rep(i, n) for(int i = 0; i < n; i++)
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<mint> a(n + 1);
	rep(i, n) {
		int x;
		cin >> x;
		a[i + 1] = a[i] + x;
	}
	mint ans = 0;
	vector<vector<mint>> ar(m + 1, vector<mint>(n + 1));
	rep(i, n + 1) ar[0][i] = 1;
	for (int j = 1; j <= m; j++)
		rep(i, n + 1) ar[j][i] = a[i] * ar[j - 1][i];
	rep(k, m + 1) {
		mint c = 1;
		rep(i, m) c *= i + 1;
		rep(i, k) c /= i + 1;
		rep(i, m - k) c /= i + 1;
		mint s = 0;
		rep(i, n + 1) {
			ans += ar[m - k][i] * s * c;
			if (k & 1)
				s -= ar[k][i];
			else
				s += ar[k][i];
		}
	}
	cout << ans.val() << endl;
}

Submission Info

Submission Time
Task F - Range Power Sum
User sounansya
Language C++ 23 (gcc 12.2)
Score 550
Code Size 805 Byte
Status AC
Exec Time 23 ms
Memory 13376 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 3448 KiB
00_sample_01.txt AC 1 ms 3480 KiB
00_sample_02.txt AC 1 ms 3472 KiB
01_random_00.txt AC 1 ms 3572 KiB
01_random_01.txt AC 14 ms 6152 KiB
01_random_02.txt AC 14 ms 6224 KiB
01_random_03.txt AC 11 ms 5924 KiB
01_random_04.txt AC 16 ms 6980 KiB
01_random_05.txt AC 15 ms 7012 KiB
01_random_06.txt AC 11 ms 6256 KiB
01_random_07.txt AC 16 ms 7900 KiB
01_random_08.txt AC 15 ms 7820 KiB
01_random_09.txt AC 12 ms 6780 KiB
01_random_10.txt AC 17 ms 8612 KiB
01_random_11.txt AC 17 ms 8676 KiB
01_random_12.txt AC 3 ms 3840 KiB
01_random_13.txt AC 18 ms 9356 KiB
01_random_14.txt AC 18 ms 9404 KiB
01_random_15.txt AC 9 ms 6532 KiB
01_random_16.txt AC 19 ms 10180 KiB
01_random_17.txt AC 19 ms 10240 KiB
01_random_18.txt AC 12 ms 7560 KiB
01_random_19.txt AC 19 ms 10984 KiB
01_random_20.txt AC 20 ms 10944 KiB
01_random_21.txt AC 12 ms 7368 KiB
01_random_22.txt AC 21 ms 11768 KiB
01_random_23.txt AC 22 ms 11740 KiB
01_random_24.txt AC 3 ms 3844 KiB
01_random_25.txt AC 22 ms 12644 KiB
01_random_26.txt AC 22 ms 12620 KiB
01_random_27.txt AC 16 ms 10172 KiB
01_random_28.txt AC 23 ms 13372 KiB
01_random_29.txt AC 23 ms 13364 KiB
02_random2_00.txt AC 23 ms 13376 KiB
02_random2_01.txt AC 23 ms 13316 KiB
02_random2_02.txt AC 23 ms 13324 KiB
03_minmax_00.txt AC 1 ms 3452 KiB
03_minmax_01.txt AC 1 ms 3528 KiB
03_minmax_02.txt AC 1 ms 3456 KiB
03_minmax_03.txt AC 1 ms 3540 KiB
03_minmax_04.txt AC 10 ms 6200 KiB
03_minmax_05.txt AC 13 ms 6304 KiB
03_minmax_06.txt AC 19 ms 13336 KiB
03_minmax_07.txt AC 23 ms 13348 KiB