AtCoder Beginner Contest 307E

ABC307E

Cycle DP. この問題のポイントは2つ．

• 最初を決め打って，一周したときに辻褄が合うようにする． 基本は line 型で考えて，最後だけ注意する．
  類題: ABC251E (記事)
• 状態をまとめること． \(0\) 番目を固定して \(i\) 番目を決めるときに，
  (\(0\) 番目と同じか異なるか) \(\in 2\)
  だけが重要． \(0\) 番目と異なる状態は，役目が全く同じなので 状態をまとめることができる．
  類題: ABC232E (記事)

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n, m ;

  cin >> n >> m;

  vector<mint> dp(2);

  dp[0] = 1;

  rep(i,n-1){ // rem: n-1

    vector<mint> old(2);

    swap(dp,old);

    // 0 : same

    dp[1] += mint(m-1)*old[0];

    dp[0] += mint(1)*old[1];

    dp[1] += mint(m-2)*old[1];

  }

  cout << (mint(m)*dp[1]).val() << endl;

  return 0;

}