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 */
下一篇: redis分布式锁