C# · 12月 19, 2021

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

题意

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

每次可以向右或向下移动

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

Sol

容斥原理

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

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

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

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

// luogu-judger-enable-o2

#include

#include

#include

#include

#include

#include

#define Pair pair

#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 '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

*/