[CF559C] Gerald and Giant Chess
程序员文章站
2022-05-08 23:51:25
...
Gerald and Giant Chess
题意:
给你一个的网格和个黑点,问你从到且不经过那个黑点的方案数,你只能向下或者向右走,答案对取模。
分析:
首先我们分析没有一个黑点的方案数,即我们只需要向下走步,向右走步。那么也就是在这步中我们选择步向下走,即方案数为。
然后我们排除掉经过那个黑点的方案数,这时我们可能会想到用容斥原理,即:
。
但是我们的范围是的,所以直接用容斥原理不可取。因为容斥原理的复杂度为。
通过上面的分析我们可以进一步优化,我们设表示从走到第个黑点,且不经过其他黑点的方案数。
那么有:
不理解的可以画一下图,很直观。
然后我们这题就能写出来了,在这之前我们还要先把黑点进行排序,因为我们看这个公式可以发现,转移方程和黑点的下标顺序有关。
我们将可以看作是第个黑点,所以代码如下:
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
ll qpow(ll a, ll b, ll mod) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll fac[maxn], inv[maxn];
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
inv[n] = qpow(fac[n], MOD - 2, MOD);
for (int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll C(int n, int m) {
if (n < m) return 0;
return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
PII p[maxn];
ll dp[maxn];
int main() {
int h, w, n;
scanf("%d%d%d", &h, &w, &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].fi, &p[i].se);
n++;
p[n].fi = h, p[n].se = w;
sort(p + 1, p + n + 1);
init(max(h, w) << 1);
for (int i = 1; i <= n; i++) {
dp[i] = C(p[i].fi + p[i].se - 2, p[i].fi - 1);
for (int j = 1; j < i; j++) {
dp[i] = ((dp[i] - dp[j] * C(p[i].fi + p[i].se - p[j].fi - p[j].se, p[i].fi - p[j].fi) % MOD) % MOD + MOD) % MOD;
}
}
printf("%lld\n", dp[n]);
return 0;
}
下一篇: node搭建服务器实现一个简单接口的调用