Znzryb's Blog
0%

ABC-399-F - Range Power Sum

Posted on Edited on

思路讲解

参考这个题解（官解看不太懂，不知道为什么可以改写成那样）

https://atcoder.jp/contests/abc399/editorial/12582

【ABC399F - Range Power Sum题解.递推】 https://www.bilibili.com/video/BV1iZZaYiEHC/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

算了，我也不尝试论述怎么想到这个思路了，这个思路还是很难想的

image

我只能说多动笔吧，分析问题，特别是dp类问题，还是需要系统的分析，光空想是不够的。

sum的定义

1
2
//      k    i   (a1+...+ai)^k+(a2+...+ai)^k+...+(ai-1+...+ai)^k+ai^k
ll sum[15][MAXN];

AC代码

https://atcoder.jp/contests/abc399/submissions/64378660

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// Problem: F - Range Power Sum
// Contest: AtCoder - AtCoder Beginner Contest 399
// URL: https://atcoder.jp/contests/abc399/tasks/abc399_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=998244353;

ll N,K,T,A[MAXN];
//      k    i   (a1+...+ai)^k+(a2+...+ai)^k+...+(ai-1+...+ai)^k+ai^k
ll sum[15][MAXN];
ll infact[15],fact[15];
ll C[15][15];

ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

inline void solve(){
	cin>>N>>K;
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,K){
		FOR(j,1,N){
			// ll idx=0;
			FOR(k,0,i-1){
				sum[i][j]+=sum[i-k][j-1]*C[k][i]%mod*binpow(A[j],k,mod)%mod;
				// ++idx;
			}
			sum[i][j]=(sum[i][j]+j*binpow(A[j],i,mod))%mod;
// #ifdef LOCAL
    // cerr << i<<" "<< j<<" "<<sum[i][j]<< '\n';
// #endif
		}
	}
	ll ans=0;
	FOR(i,1,N){
		ans=(ans+sum[K][i])%mod;
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	fact[0]=1,infact[0]=1;
	FOR(i,1,13){
		fact[i]=fact[i-1]*i%mod;
		infact[i]=binpow(fact[i],mod-2,mod);
	}
	FOR(i,1,13){
		FOR(j,0,i){
			C[j][i]=fact[i]*infact[j]%mod*infact[i-j]%mod;
		}
	}
// #ifdef LOCAL
    // FOR(i,1,13){
		// FOR(j,0,i){
			// cerr<<C[j][i]<<" ";
		// }
		// cerr<<"\n";
	// }
// #endif
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc399/submissions/64378660
*/

心路历程（WA，TLE，MLE……）

一种比较常见的递推思路是

长度为1的区间→长度为2的区间→…→长度为n的区间（很正常的想法）