ABC307 E問題解説(Python)

E問題 Distinct Adjacent

問題
1 からN の番号がついたN 人の人が輪になってならんでいます。
人1 の右隣には人2 が、人2 の右隣には人3 が、……、人N の右隣には人1 がいます。
N 人の人にそれぞれ 0 以上 M 未満の整数を 1 つずつ渡します。M N 通りの渡し方のうち、どの隣り合う 2 人が渡された数も異なるものの数を、998244353 で割ったあまりを求めてください。

制約
・2≤ N, M ≤10^6
・N,M は整数である

提出コード

mod=998244353
n,m=map(int,input().split())
dp=[[0,0] for i in range(n)]
dp[0][1]=1
 
for i in range(1,n):
    dp[i][0]+=dp[i-1][0]*(m-2)%mod
    dp[i][0]+=dp[i-1][1]*(m-1)%mod
    dp[i][1]+=dp[i-1][0]%mod
 
print(dp[n-1][0]*m%mod)

N=5, M=4を例にして考える

1人目に割り当てる数字を0と決めうちする。(最後にM倍すれば答えになる)

DPテーブルを以下のように考える
DP[i][f]= i 人目まで数を割り当てる方法のうち、i人目まで隣が同じ数にならないパターン数
ただしf=True ：i人目が1人目と同じ数
　　　f=False ：i人目が1人目と違う数

N=5 M=4の時のDPテーブル

上の図を見るとわかりやすいが計算式は次のようになる
DP[i][True]=DP[i-1][False]
DP[i][False]=DP[i-1][True]*(M-1)+DP[i-1][False]*(M-2)

0を決めうちしたので答えはM倍して
DP[-1][False]*M mod 998244353となる

メモ

・DPテーブルを書いたら理解できた
・円環DPは最後の辻褄合わせ(１とN)に着目する