专栏文章

题解：AT_abc399_f [ABC399F] Range Power Sum

FFire_flame
AT_abc399_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miprs90w
此快照首次捕获于
2025/12/03 16:53
3 个月前
此快照最后确认于
2025/12/03 16:53
3 个月前
查看原文
题目传送门

Solution\mathtt{Solution}

简单题。
观察这个式子的形式，发现它可以用二项式定理拆开。
记 si=∑j=1iais_i=\sum\limits_{j=1}^{i}a_i，其中 s0=0s_0=0，那么原式可表示为：∑1≤ l≤ r≤ n(sr−sl−1)k\displaystyle\sum_{1\leq\ l\leq\ r\leq\ n}(s_r-s_{l-1})^k。
由于 kk 不超过 1010，那么我们可以用二项式定理展开。
(sr−sl−1)k= ∑i=0kCki sri sl−1k−i (−1)i(s_r-s_{l-1})^k=\displaystyle\ \sum_{i=0}^{k}C_k^i\ s_r^i\ s_{l-1}^{k-i}\ (-1)^i
由于 Cki sri (−1)iC_k^i\ s_r^i\ (-1)^i 可以提出来，那么只需要枚举 rr，然后前缀和优化就可以了。
赛时代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int s = 0, f = 1;char ch = getchar();
	while(!isdigit(ch)){if(ch == '-')f = -1;ch = getchar();}
	while(isdigit(ch)){s = s * 10 + ch - '0';ch = getchar();}
	return s * f;
}
void write(int x){
    if(x < 0){putchar('-'); x = -x;}
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const int MAXN = 2e5 + 5, MOD = 998244353;
int n, k, ans, a[MAXN], s[MAXN], fac[MAXN], inv[MAXN], sum[MAXN];
int fpow(int a, int b){
	int res = 1;
	while(b){
		if(b & 1ll)res = res * a % MOD;
		a = a * a % MOD;
		b = b >>= 1ll;
	}
	return res;
}
int C(int x, int y){
	if(x < y)return 0;
	return fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}
signed main(){
	n = read(), k = read();
	for(int i = 1;i <= n;i ++)a[i] = read(), s[i] = (s[i - 1] + a[i]) % MOD;
	fac[0] = 1;
	for(int i = 1;i <= 2e5;i ++)fac[i] = fac[i - 1] * i % MOD;
	inv[200000] = fpow(fac[200000], MOD - 2);
	for(int i = 2e5 - 1;i >= 0;i --)inv[i] = inv[i + 1] * (i + 1) % MOD;
	for(int i = 0;i <= n;i ++){
		for(int j = 0;j <= k;j ++){
			ans += C(k, j) * sum[j] % MOD * fpow(-1, j) % MOD * fpow(s[i], k - j) % MOD;
			ans %= MOD;
			ans += MOD;
			ans %= MOD;
			sum[j] += fpow(s[i], j), sum[j] %= MOD;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...