多數題解提到隨機遊走 N 步距原點期望距離是 $\sqrt{N}$ 級別，且本題只知級別無用，常數也很重要。實際上只知道期望沒有多大用，應該分析隨機遊走不超過設定閾值的概率。

寫一程序計算**隨機遊走 N 步，不超過 [-i, i]**之概率：

#include <iostream>
#include <vector>

using REAL = double;

int main()
{
  int N;
  std::cin >> N;
  std::vector f(N * 2 + 1, std::vector<REAL>(N + 1));
  f[N][0] = 1.;
  for (int i = 0; i < N; i++) {
    std::vector g(N * 2 + 1, std::vector<REAL>(N + 1));
    for (int j = -i; j <= i; j++) {
      for (int k = 0; k <= i; k++) {
        g[j + 1 + N][std::max(k, std::abs(j + 1))] += f[j + N][k] / 2;
        g[j - 1 + N][std::max(k, std::abs(j - 1))] += f[j + N][k] / 2;
      }
    }
    f = std::move(g);
  }

  std::vector<REAL> fm(N + 1);
  for (int i = -N; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
      fm[j] += f[i + N][j];
    }
  }

  std::vector<REAL> sfm(N + 2);
  for (int i = 0; i <= N; i++) sfm[i + 1] = sfm[i] + fm[i];

  for (int i = 0; i <= N; i++) std::cout << i << " " << sfm[i + 1] << std::endl;
}

N=100 結果如下：

0 0
1 8.88178e-16
2 7.55096e-07
3 0.000439825
4 0.00856466
5 0.0388333
6 0.101347
7 0.180581
8 0.276862
9 0.365852
10 0.459241
11 0.535991
12 0.613461
13 0.673486
14 0.733588
15 0.778166
16 0.822748
17 0.854486
18 0.886224
19 0.907912
20 0.9296
21 0.943821
22 0.958043
23 0.966988
24 0.975934
25 0.98133
26 0.986726
27 0.989845
28 0.992965
29 0.994692
30 0.99642
31 0.997336
32 0.998253
33 0.998718
34 0.999182
35 0.999408
36 0.999634
37 0.999738
38 0.999843
39 0.999889
40 0.999936
41 0.999955
42 0.999975
43 0.999983
44 0.999991
45 0.999994
46 0.999997
47 0.999998
48 0.999999
49 0.999999
50 1
51 1
52 1
53 1
54 1
55 1
56 1
57 1
58 1
59 1
60 1
61 1
62 1
63 1
64 1
65 1
66 1
67 1
68 1
69 1
70 1
71 1
72 1
73 1
74 1
75 1
76 1
77 1
78 1
79 1
80 1
81 1
82 1
83 1
84 1
85 1
86 1
87 1
88 1
89 1
90 1
91 1
92 1
93 1
94 1
95 1
96 1
97 1
98 1
99 1
100 1

隨機遊走 N 步不超過很多題解設的 [-20, 20] 的概率是 0.9296，特別小，哪怕設成剛好卡滿 long long 的 [-31,31] 都只有 0.999936，交幾百發就掛了。

怎麼回事？？？