AtCoder Beginner Contest 275E

e

ABC275E

ちょうど \(i \in K+1\) 回で \(j \in N+1\) に居る確率を DP で求める． どの様な手順でその局面に至ったかは，今後に影響しないので， 状態をまとめることが出来てDP可能．
遷移に \(O(M)\)．

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

int main() {

  ll n, m, k;

  cin >> n >> m >> k;

  mint inv = mint(1) / mint(m);

  vector<mint> dp(n+1);

  mint ans;

  dp[0] = 1;

  rep(i,k) {

    vector<mint> old(n+1);

    swap(dp, old);

    rep(j,n) rep1(l,m){

      ll nj = j + l;

      if(nj > n){

        nj = n - (nj-(n));

      }

      dp[nj] += old[j] * inv;

    }

    ans += dp[n];

  }

  cout << ans.val() << endl;

  return 0;

}