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

迷南。 2023-10-11 13:02 35阅读 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;
    }