专栏文章

题解：AT_abc399_f [ABC399F] Range Power Sum

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miprs01j
此快照首次捕获于
2025/12/03 16:53
3 个月前
此快照最后确认于
2025/12/03 16:53
3 个月前
查看原文
题目链接
这次的F题有点难度，估计可以评个绿题吧。

思路

此题可以用DP+二项式定理解决。
我们设 dpr,k=∑l=1r(∑i=lrAi)kdp_{r,k} = \sum^r_{l = 1} (\sum^r_{i = l} A_i)^k ，然后我们考虑转移。
dpr+1,k=∑i=lr+1(∑i=lr+1Ai)kdp_{r + 1, k} = \sum^{r + 1}_{i = l} (\sum^{r + 1}_{i = l} A_i)^k
             =Ar+1k+∑i=1r(∑i=1rAi+Ar+1)k\space\space\space\space\space\space\space\space \space\space\space\space\space = A_{r + 1}^k + \sum^r_{i = 1} (\sum^r_{i = 1} A_i + A_{r + 1}) ^ k
然后根据二项式定理 (x+y)k=∑j=1k(kj)xjyk−j(x + y) ^ k = \sum^k_{j = 1}\binom{k}{j}x^jy^{k - j} :
如果我们将 ∑i=1rAi\sum^r_{i = 1} A_i 看做 xx ， Ar+1A_{r + 1} 看做 yy 。
那么原式就变成了：
    Ar+1k+∑l=1r∑i=lr(kj)(∑j=1kAi)jAr+1k−j\space\space\space\space A_{r + 1}^k + \sum^r_{l = 1} \sum^r_{i = l} \binom{k}{j} (\sum^k_{j = 1}A_i) ^ j A_{r + 1} ^ {k - j}
=Ar+1k+∑j=1k(kj)∑l=1r(∑i=lrAi)jAr+1k−j=A_{r + 1}^k + \sum^k_{j = 1} \binom{k}{j} \sum^r_{l = 1} (\sum^r_{i = l} A_i) ^ j A_{r + 1} ^ {k - j}
然后观察一下中间的这个式子 ∑l=1r(∑i=lrAi)j\sum^r_{l = 1} (\sum^r_{i = l} A_i) ^ j ， 这不就是 dpr,jdp_{r,j} 吗！
所以最后的转移方程就长这样：
dpi+1,j=Ar+1k+∑j=1k(kj)dpr,jdp_{i + 1,j} = A_{r + 1}^k + \sum^k_{j = 1} \binom{k}{j} dp_{r, j}
最终的结果就是 ∑i=1ndpi,k\sum^n_{i = 1} dp_{i, k} 。

代码

CPP
#include <bits/stdc++.h>

#define endl '\n'
#define int long long

const int Mod = 998244353;

signed main (void) {
	
	std :: ios :: sync_with_stdio (false);
	std :: cin.tie (nullptr);
	std :: cout.tie (nullptr);
	
	int N, K;
	
	std :: cin >> N >> K;
	
	std :: vector <int> A (N + 1);
	
	for (int i = 1; i <= N; ++ i) {
		
		std :: cin >> A[i];
	}
	
	std :: vector <std :: vector <int> > F (K + 1);
	
	F[0].resize (K + 1);
	F[0][0] = 1;
	
	for (int i = 1; i <= K; ++ i) {
		
		F[i].resize (K + 1);
		
		F[i][0] = F[i][i] = 1;
		
		for (int j = 1; j < i; ++ j) {
			
			F[i][j] = F[i - 1][j] + F[i - 1][j - 1] % Mod;
		}
	} 
	
	std :: vector <int> Result (K + 1), Presult (K + 1), Comb (K + 1);
	
	int Answer = 0;
	
	for (int i = 1; i <= N; ++ i) {
		
		Comb[0] = 1;
		
		for (int j = 1; j <= K; ++ j) {
			
			Comb[j] = Comb[j - 1] * A[i] % Mod;
		}
		
		for (int k = 0; k <= K; ++ k) {
			
			Result[k] = Comb[k];
			
			for (int j = 0; j <= k; ++ j) {
				
				Result[k] = (Result[k] + Presult[j] * F[k][j] % Mod * Comb[k - j]) % Mod;
			}
		}
		
		Answer += Result[K];
		Answer %= Mod;
		
		Presult = Result;
	}
	
	std :: cout << Answer << endl;
	
	return 0;
}
完结撒花🎉🎉🎉

评论

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

正在加载评论...