欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

cf559C. Gerald and Giant Chess(容斥原理)

程序员文章站 2022-04-09 18:40:23
题意 $h \times w$的网格,有$n$个障碍点, 每次可以向右或向下移动 求从$(1, 1)$到$(h, w)$不经过障碍点的方案数 Sol 容斥原理 从$(1, 1)$到$(h, w)$不经过障碍点的方案数为$C(h + w, h)$ 设$f[i]$表示到达第$i$个黑格子的合法路径的方案 ......

题意

$h \times w$的网格,有$n$个障碍点,

每次可以向右或向下移动

求从$(1, 1)$到$(h, w)$不经过障碍点的方案数

sol

容斥原理

从$(1, 1)$到$(h, w)$不经过障碍点的方案数为$c(h + w, h)$

设$f[i]$表示到达第$i$个黑格子的合法路径的方案数

首先对所有点按$x$排序,这样就能保证每次从他的左上方转移而来

然后根据公式算一下就好了

// luogu-judger-enable-o2
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long 
//#define int long long
using namespace std;
const int maxn = 3 * 1e6, mod = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
pair p[maxn];
int h, w, n;
int fac[maxn], ifac[maxn], f[maxn];
int fastpow(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base % mod;
}
int c(int n, int m) {
    return (fac[n] * ifac[m] % mod * ifac[n - m]) % mod;
}
main() {
    h = read(), w = read(); n = read() + 1; 
    fac[0] = 1; for(int i = 1; i <= h + w; i++) fac[i] = i * fac[i - 1] % mod;
    ifac[h + w] = fastpow(fac[h + w], mod - 2); 
    for(int i = h + w; i >= 1; i--) ifac[i - 1] = i * ifac[i] % mod;
    for(int i = 1; i <= n - 1; i++) {
        int x = read(), y = read();
        p[i] = mp(x, y);
    }
    p[n] = mp(h, w);
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n; i++) {
        f[i] = c(p[i].fi + p[i].se - 2, p[i].fi - 1);
        for(int j = i - 1; j >= 1; j--) {
            if(p[j].se <= p[i].se) {
                int x = p[i].fi - p[j].fi + 1, y = p[i].se - p[j].se + 1;
                (f[i] -= f[j] * c(x + y - 2, x - 1) % mod + mod) %= mod;
            }
        }
    }
    printf("%i64d", (f[n] + mod) % mod);
    return 0;
}
/*
2 3 2
2 1
2 2
*/