AtCoder ARC #114 : C - Sequence Scores

Eが解けなかったのが痛い。
https://atcoder.jp/contests/arc114/tasks/arc114_c

問題

整数列Aに対し、f(A)は以下のように定める。

初期状態でAは全要素0とする。
区間[L,R]と値vを定め、L≦x≦Rに対し、A[x]=max(A[x],v)で更新する、という作業を行う。
f(A)は、そのAを再現するための必要作業回数の最小値とする。

N要素で、全要素1～Mである数列A、N^M通りにおけるf(A)の総和を求めよ。

解法

ある値A[x]=vを作るために、追加で1回作業が必要かどうかと考えよう。

• xより手前にA[y]=vとなるyがあり、かつy≦z≦xとなるzにA[z]＞vとなるzがなければ、追加作業は不要(A[y]を作るのと同時にA[x]を作れる)
• それ以外なら、1手必要

g(x,v)を1手必要となるAの構成法の組み合わせとすると、g(*,v)をO(N)で構築できる。
よってg(*,*)は全体でO(NM)で構築できる。

int N,M;
const ll mo=998244353;

//ll dp[5050][5050];
ll p[5050][5050];
ll dp[5050][5050][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,5010) {
		p[i][0]=1;
		FOR(j,5010) p[i][j+1]=p[i][j]*i%mo;
	}
	
	cin>>N>>M;
	
	ll ret=0;
	for(i=1;i<=M;i++) {
		dp[i][0][0]=1;
		for(j=1;j<=N;j++) {
			dp[i][j][0]=(dp[i][j-1][0]*(M-1)+dp[i][j-1][1]*(M-i))%mo;
			dp[i][j][1]=(dp[i][j-1][0]*1+dp[i][j-1][1]*i)%mo;
			(ret+=dp[i][j-1][0]*p[M][N-j])%=mo;
		}
		
	}
	
	
	cout<<ret<<endl;
}

まとめ

こちらはちょっと手間取ったけどまぁまぁの時間で解けたのよね。