Codeforces 559C - Gerald and Giant Chess 【计数DP】-蒲公英云

Codeforces 559C - Gerald and Giant Chess 【计数DP】

迷南。 2023-10-11 13:02 120阅读 0赞

题目描述

假设虚伪有一个h行w列的棋盘，棋盘上的格子有的是可以经过的，有的是不可以经过的。一开始在棋盘的左上角（第一行第一列）有一颗棋子，这颗棋子每次只能往右或者往下移动一格。那么虚伪要将其从起点移动到右下角( h，w) 一共有多少种移法？

输入

第一行输入三个整数：h，w，n (1<=h，w<=10^5，1<=n<=2000)。

分别代表h行w列的棋盘，棋盘上一共有n个不可经过的点。接下来n行中，每一行有两个整数xi，yi。代表在棋盘中的第xi行，第yi列所在的格子是不可经过的。

输出

输出移动的方法数，结果请对1000000007取余数。

思路：不考虑黑色格子的话就是一个经典DP问题，对于n行m列来说，左上走到右下的方案数就是C(n + m - 2, n - 1) ，因为总共要走n + m - 2步，向下n-1次，向右m-1次，所以就是它们组成的序列，它们之间的顺序是任意的，所以就得到一个排列式。

将黑色格子按照x升序，y升序排序，我们设F[i] 表示第一次走到的黑色格子是第i个的方案数，那么对于任意i

F[i] = F[i] - F[j] * C(xi + yi - xj - yj, xi - xj) (j < i) , 其中F[i] = C(xi + yi - 2, xi - 1), 目标就是F[n + 1]

可以这样理解它的状态，对于任意的i，我们需要去除重复计算的，就是之前经过某个黑色格子j，方案是F[j]，然后从j到i的方案又是C(xi + yi - xj - yj, xi - xj), 所以F[i] - F[j] * C(xi + yi - xj - yj, xi - xj).

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define ls rt << 1
#define rs rt << 1|1
#define mid ((l + r) >> 1)
#define lson l, mid, ls
#define rson mid + 1, r, rs
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
ll p[maxn], q[maxn]; //p是阶乘，q是阶乘的逆元
ll powermod(ll a, ll b, ll c)
{
    ll ans = 1;
    a = a % c;
    while(b)
    {
        if(b&1)
            ans = ans * a % c;
        b >>= 1;
        a = a * a % c;
    }
    return ans % c;
}
void init()
{
    p[0] = q[0] = 1;
    for(int i = 1; i < maxn; ++i)
        p[i] = (p[i - 1] * i) % mod;
    q[maxn - 1] = powermod(p[maxn - 1], mod - 2, mod);
    for(int i = maxn - 1; i > 0; --i)
        q[i - 1] = q[i] * i % mod;
}
ll C(ll n, ll m) //C(n, m) n是底数
{
    if(n < m)
        return 0;
    return p[n] * q[m] % mod * q[n - m] % mod;
}
struct node
{
    ll x, y;
    bool operator < (const node &r) const
    {
        if(x == r.x) return y < r.y;
        return x < r.x;
    }
}a[maxn];
ll f[maxn];
int main()
{
    init();
    ll h, w, n;
    scanf("%lld%lld%lld", &h, &w, &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lld%lld", &a[i].x, &a[i].y);
    sort(a + 1, a + n + 1);
    a[n + 1].x = h, a[n + 1].y = w;
    for(int i = 1; i <= n + 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[j].x <= a[i].x && a[j].y <= a[i].y)
                f[i] = (f[i] - f[j] * C(a[i].x + a[i].y - a[j].x - a[j].y, a[i].x - a[j].x) % mod + mod) % mod;
        }
    }
    ll ans = (f[n + 1] + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}