AT_abc399_f

感觉赛时脑梗了

记

s_i = \sum\limits_{1 \le j \le i} a_j

\sum\limits_{i > j \ge 1}(s_i - s_j) ^ k

= \sum\limits_{i > j \ge 1}\sum\limits_{0\le l \le k} \binom{k}{l} s_i^l s_j^{k - l}(-1)^{k - l}

= \sum\limits_{0\le l \le k} \binom{k}{l}(-1)^{k-l}s_i^l \sum\limits_{1\le j < i}s_j^{k - l}

计算时维护

\sum\limits_{1 \le j < i} s_j ^ {k - l}

最后再加上

\sum s_i^k

即可

code:

CPP

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 2e5 + 5, mod = 998244353;
int sum[maxn], val[15], n, k;
int c[15][15];
void init() {
	c[0][0] = 1;
	for (int i = 1; i <= 10; ++i) {
		for (int j = 0; j <= 10; ++j) {
			c[i][j] = c[i - 1][j];
			if (j) c[i][j] += c[i - 1][j - 1];
			c[i][j] %= mod;
		}
	}
}
int qpow(int a, int b) {
	int res = 1;
	for (int t = a; b; b >>= 1, t = (t * t) % mod) {
		if (b & 1) res = (res * t) % mod;
	}
	return res;
}
int add(int x, int y) {
	// return x + y;
	return ((x + y) % mod + mod) % mod;
}
signed main() {
	cin >> n >> k;
	init();
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		sum[i] = add(sum[i - 1], x);
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (int l = 0; l <= k; ++l) {
			int cur = val[k - l];
			int f = (c[k][l] * ((k - l) & 1 ? -1 : 1) + mod) % mod;
			ans = add(ans, f * qpow(sum[i], l) % mod * cur % mod);
		}
		for (int l = 0; l <= k; ++l) {
			val[l] = add(val[l], qpow(sum[i], l));
		}
	}
	for (int i = 1; i <= n; ++i) {
		ans = add(ans, qpow(sum[i], k));
	}
	cout << ans << endl;
	return 0;
}

文章操作

相关推荐

评论

AT_abc399_f