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

*/

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!