ARC114 - Sequence Scores

题目大意：对于一个序列$A=a_i,a_i\in[1,m]$，定义$f(A)$为

对于一个全零的初始序列，每次选择一个区间对于某一个值取$\max$，最少生成$A$的步数

求所有$m^n$种$A$的$f(A)$之和

首先考虑$f(A)$的计算，显然可以采用如下方法

1
2
3
4
5
6
7
b[i]=0
Function Solve(l,r)
	v=min a[l..r]
	for i in l,r
		b[i]=max{b[i],v}
	Divide a[l..r] into contiguous ranges that a[i]!=b[i] , Solve(l',r')

那么考虑计算一个区间$[l,r]$被$\text{Solve}$的次数

显然区间$[l,r]$被$\text{Solve}$当且仅当

$\min\{a_i|i\in[l,r]\}>\max(a_{l-1},a_{r+1})$

对于不同的$r-l+1$，枚举$\min$，计算方案数即可

注意考虑$l=1\or r=n$的边界情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=5010,P=998244353;

int n,m;
int Pow[N][N],F[N][3];

int main(){
	n=rd(),m=rd();
	rep(i,0,N-1) rep(j,*Pow[i]=1,N-1) Pow[i][j]=1ll*Pow[i][j-1]*i%P;
	rep(i,1,n) rep(j,0,2) rep(k,1,m) {
		F[i][j]=(F[i][j]+1ll*(Pow[m-k+1][i]-Pow[m-k][i]+P)*Pow[k-1][j])%P;
	}
	int ans=0;
	rep(i,1,n) rep(j,i,n) {
		int c=(i>1)+(j<n);
		ans=(ans+1ll*F[j-i+1][c]*Pow[m][n-(j-i+1)-c])%P;
	}
	printf("%d\n",ans);
}