杰拉尔德和巨型象棋
C++ 代码
/*
本题要求我们从左上角走到右下角并绕开黑色格子的路线数量。
设 C(a, b) 表示从 a 个数中选 b 个数的方案数
棋盘上白色格子数量巨大,而黑色格子最多只有 2000 个,我们应该考虑如何依靠黑色格子进行计数,
如果这个卒能走进黑色格子,那么左上角走到右下角的路线总数就是 C(H + W - 2, H - 1),从左上角
走到右下角一共需要 H + W - 2 步,其中必须要向右走 W - 1 步,向下走 H - 1 步,根据在不同时机
向下走就能得到所有的路线,而 H + W - 2 步中任选 H - 1 步向下走的方案数量就是 C(H + W - 2, H - 1),
也就是从左上角走到右下角且不经过黑色格子的路线总数。
若我们再求出从左上角到右下角经过了至少一个黑色格子的路线数量,二者相减就得到了只经过白色格子
的路线数。
把所有黑色格子按照行、列坐标递增的顺序排序,我们假设左上角是第 0 个黑色格子,右下角是第 n + 1 个
黑色格子,设第 i 个黑色格子在第 x[i] 行第 y[i] 列。
设 f[i] 表示从左上角走到排序后第 i 个黑色格子,并且途中不经过其他黑色格子的路线数。
f[i] = C(x[i] - 1 + y[i] - 1, x[i] - 1) - sum{ f[j] * C(x[i] - x[j] + y[i] - y[j], x[i] - x[j]) } (1 <= j < i, x[i] >= x[j], y[i] >= y[j])
上式的含义是枚举 j 作为从左上角到 (x[i], y[i]) 经过的第一个黑色格子。也就是从左上角到 (x[j], y[j])
不能经过其他黑色格子,路线为 f[j]。从 (x[j], y[j]) 到 (x[i], y[i]) 随便走,路线就是一个组合数。
等式中求和符号的部分求出了从左上角到 (x[i], y[i]),途中经过至少一个黑色格子的路线数,用总数减掉,
就得到了 f[i]
为什么这样设计状态转移方程?为什么限制 j 作为经过的第一个黑色格子呢?
一个状态划分成的若干个子问题之间应该具有互斥性,才不会造成重复统计,我们在求解像本题这样的计数类 dp 时,
通常要找到一个 “基准点”,围绕这个基准点构造一个不可划分的 “整体”,以避免子问题之间的重叠。既然需要求出
从左上角到 (x[i], y[i]) 途中经过至少一个黑色格子的路线数,就枚举第一个经过的黑色格子 j,使左上角到 j
构成一个整体,让这段路程只能经过白色格子,不能再进行拆分。因为第一个经过的黑色格子不同,所以不同的 j
对应的路线肯定不会重复,而 j 又取遍了 i 之前的所有黑色格子,所以路线也不会遗漏。由此我们得到了上式的
状态转移方程
以 f[0] = 1 为初始状态,计算上面的状态转移方程,f[n + 1] 就是目标状态,对于组合数,可以预处理阶乘关于 1e9+7
的乘法逆元来计算
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2010, M = 200010, mod = 1e9 + 7;
int n, m, k;
int f[N]; //设 f[i] 表示从左上角走到排序后第 i 个黑色格子,并且途中不经过其他黑色格子的路线数
int fact[M], infact[M]; //记录阶乘和阶乘的逆元
struct Node
{
int x, y; //坐标
bool operator< (const Node &t) const
{
return x < t.x || (x == t.x && y < t.y); //将所有黑色格子按行、列坐标递增顺序排序
}
}a[N]; //存储所有黑色格子
int qmi(int a, int k) //快速幂
{
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
k >>= 1;
}
return res;
}
void init() //预处理阶乘和阶乘的逆元
{
fact[0] = 1, infact[0] = 1;
for(int i = 1; i < M; i++)
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = qmi(fact[i], mod - 2);
}
}
int C(int a, int b) //组合数 C(a, b) = fact[a] * infact[b] * infact[a - b]
{
return (LL)fact[a] * infact[b] % mod * infact[a - b] % mod;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
init(); //预处理阶乘和阶乘的逆元
for(int i = 1; i <= k; i++) scanf("%d%d", &a[i].x, &a[i].y);
sort(a + 1, a + 1 + k); //将所有黑色格子按行、列坐标递增顺序排序
a[k + 1] = {n, m}; //令右下角是黑色格子,用于转移终点状态
//计数 dp
for(int i = 1; i <= k + 1; i++)
{
f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
for(int j = 1; j < i; j++)
{
if(a[i].x < a[j].x || a[i].y < a[j].y) continue; //跳过不合法状态
f[i] = (f[i] - (LL)f[j] * C(a[i].x - a[j].x + a[i].y - a[j].y, a[i].x - a[j].x)) % mod;
}
}
printf("%d\n", (f[k + 1] + mod) % mod); //答案可能为负,需要处理一下
return 0;
}
tql