【今日の精進】ARC114C - Sequence Scores

毎日格上の問題を倒すやつの92日目です。

問題リンク

atcoder.jp

問題概要

長さが で要素が 以上 以下である数列すべてについて、以下の値の和を で割ったあまりを求めてね。

• 長さが で要素がすべて である数列から、「ある区間の数をその数と決めた数の大きい方で置き換える」ことを繰り返したとき、数列を作る最小の操作数

解法

ある数を右に追加して、操作回数が増えるかどうかを考えます。

操作回数が増えない条件は、それより左が

• その数より真に大きいがいくつか
• その数が1つ
• その数以下がいくつか

という数列になっているときです。これはDPで差分を計算できます。

提出コード

MOD=998244353
N,M=map(int,input().split())
dp=[0]*M
powm=[1]*(N+1)
for i in range(N):
    powm[i+1]=(powm[i]*M)%MOD
ans=0
for i in range(N):
    for j in range(M):
        ans+=powm[N-1]-dp[j]*powm[N-i-1]
        dp[j]*=(M-j-1)
        dp[j]+=powm[i]
        dp[j]%=MOD
    ans%=MOD
print(ans)

Submission #48683723 - AtCoder Regular Contest 114

感想

この回出てたら2500パフォくらい出てたらしく、涙…*1

*1:Eも解けてるので