ARC114 - Sequence Scores

Posted on Edited on In

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);
}