Sugoroku 4

题意

有一行格子，编号为 \(0, 1, \cdots n\)，你站在 \(0\) 号格子上。

你手上有一个转盘，转盘上写有数字 \(1 \sim m\)，每次转转盘后显示的数值是等概率出现的。

假设某次转转盘后转盘显示的数值为 \(x\)，你会行走 \(x\) 步，当你走到第 \(n + 1\) 个格子时，你会回头行走剩余步数，形同飞行棋的最后几步。

当你在某次走完后恰好停在第 \(n + 1\) 个格子上时游戏结束，你最多转 \(k\) 次转盘，问胜利的概率对 \(998244353\) 取模的结果。

数据范围

\(1 \leqslant n, k \leqslant 1000\)。
\(1 \leqslant m \leqslant \min(n, 10)\)。

思路

一个明显的概率 dp。

提到等概率和取模，不难想到费马小定理，转盘上显示某个数的概率为 \(\frac{1}{m}\)，根据费马小定理可得 \(\frac{1}{m} \equiv \frac{1}{m} \times m ^ {998244353 - 1} \equiv m ^ {998244353 - 2} \equiv m ^{998244351} \pmod{998244353}\)，可以用快速幂求，下面用 \(qp\) 表示。

定义 \(F_{i,j}\) 表示 \(i\) 是否可以转一次转盘走到 \(j\)，如果是则为 \(1\)，否则为 \(0\)。

状态：\(dp_{i, j}\) 表示转了 \(i\) 次转盘走到编号为 \(j\) 的格子的概率。
转移：\(dp_{i, j} = \sum\limits_{0 \leqslant k < n} F_{k, i} \times dp_{i - 1, k} \times qp\)，你也可以思考一下扩散性转移。
初始状态：\(dp_{0, 0} = 1\)。
目标状态：\(\sum\limits_{1 \leqslant i \leqslant k} dp_{i, n}\)。

注意取模和乘法爆 int 的细节即可。

复杂度

时间：\(O(n \times m \times k)\)。
空间：\(O(n \times k)\)。

Code

点击查看代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mod = 998244353, N = 1e3 + 10;

int n, m, k;
ll qp, dp[N][N], ans;

ll qmod (ll a, int b) { // 快速幂求 qp
  ll ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod, b >>= 1;
  }
  return ans;
}

int Q (int x, int t) { // 求按规则从 x 往后走 t 步会走到的格子的编号
  if (x + t <= n) { // 不用回头
    return x + t;
  }
  return 2 * n - t - x; // 回头
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> k;
  qp = qmod(m, mod - 2), dp[0][0] = 1;
  for (int i = 0; i < k; i++) { // 扩散形转移好写
    for (int j = 0; j < n; j++) {
      for (int l = 1; l <= m; l++) { // 枚举走多少步
        dp[i + 1][Q(j, l)] = (dp[i + 1][Q(j, l)] + dp[i][j] * qp) % mod; // 取模!
      }
    }
  }
  for (int i = 1; i <= k; i++) {
    ans = (ans + dp[i][n]) % mod;
  }
  cout << ans;
  return 0;
}