钉子和小球
题意
如图的三角形木板上钉着 \(\dfrac{n(n+1)}{2}\) 个钉子,还有 \((n+1)\) 个格子,钉子均匀分布,其中有一些钉子被拆掉,问最后小球落在 \(m\) 格子的概率为多少?
分析
概率DP,把格子也看作钉子。
设 \(f(i, j)\) 表示经过 \((i, j)\) 位置的所有路径数量,那么到达 \(m\) 格子的概率就是 \(f(n+1, m) / f(1, 1)\) ,这是因为任何一个路径一定经过 \((1, 1)\) ,所以 \(f(1, 1)\) 为 \(2^n\) 。
对于一个位置 \((i, j)\) ,如果它有钉子,那么可以转移到左下角 \((i+1, j)\) 或者右下角 \((i+1, j+1)\) ,路径数量为一半。
如果它没有钉子,那么它会直接转移到下面正对着的两行的位置 \((i+2, j+1)\) 。
我们可以从上往下枚举。
注意初始化 \(f(1, 1)\) 和 \(f(2, 1) 、 f(2, 2)\) 。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 55;
bool ext[N][N]; // 表示在(i, j)这个位置有无钉子
ll f[N][N]; // f(i, j) 表示存在(i, j)的路径的数量
void solve ()
{
int n, m; cin >> n >> m; m += 1;
f[1][1] = (1ll << n+1);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
{
char c; cin >> c;
if (c == '*') ext[i][j] = true;
}
if (ext[1][1]) f[2][1] = f[2][2] = (1ll << n);
// 每个位置有三种情况
for (int i = 3; i <= n + 1; i ++ )
{
for (int j = 1; j <= i; j ++ )
{
f[i][j] = f[i-1][j-1] / 2 * ext[i-1][j-1] + \
f[i-1][j] / 2 * ext[i-1][j] + \
f[i-2][j-1] * (!ext[i-2][j-1]);
}
}
ll g = __gcd(f[n+1][m], f[1][1]);
cout << f[n+1][m] / g << '/' << f[1][1] / g << endl;
}
signed main ()
{
cout.tie(0)->sync_with_stdio(false);
// int _; for (cin >> _; _ --; ) solve();
solve();
return 0;
}