Submission #42931163

---

Source Code Expand

import std;

void read(T...)(string S, ref T args) {
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

void main () {
    int N, M; readln.read(N, M);
    solve(N, M);
}

void solve (int N, int M) {
    const MOD = 998244353;
    long[][] dp = new long[][](N, 2);
    // dp[i][j] := 状態jでi人目に行く場合の数 (j=0は最初の人と同じ j=1は最初の人と違う数字)

    // initialize
    dp[0][0] = M;
    dp[0][1] = 0;

    foreach (i; 1..N) {
        dp[i][0] = dp[i-1][1];
        dp[i][1] = (M-1) * dp[i-1][0] + (M-2) * dp[i-1][1];
        dp[i][] %= MOD;
    }

    writeln(dp[$-1][1]);
}

Submission Info

Judge Result