LOJ6614 THUPC 2019 过河卒二（chess）
题目链接
题目大意
给你一个 $n$ 行 $m$ 列的棋盘，从 $(1, 1)$ 走到 $(n, m)$ ，有 $k$ 个点不能经过，每次可以向上向右或者向斜上方走。问有多少走法可以走出棋盘。结果对 $59393$ 取模。
题目分析
由于所有的路径均需走出棋盘，那么显然只会走到 $n + 1$ 行或者 $m + 1$ 列，那么显然如果不允许他们继续走向其他的行或列，那么显然走出去后都有唯一的路径走到 $(n + 1, m + 1)$ 点。也就是说，题目便转化为从 $(1, 1)$ 走到 $(n + 1, m + 1)$ 。
此时再考虑从$(0, 0)$ 走到 $(x, y)$ ，显然需要走 $x$ 步向上， $y$ 步向右，由于还有可能斜着走，注意到 $m$ 是 $10 ^ 5$ 量级的。因此可以枚举斜着走的次数，那么可以获得如下表达式：
$$\sum\limits_{i=0}^{\min(x, y)}{C_{x + y – 2i}^{x – i} \cdot C_{x + y – i}^{i}}$$
注意到 $n$ 是 $10 ^ 9$ 量级的，而模数是 $59393$，因此需要使用 $Lucas$ 定理来求组合数。
之后考虑不经过 $k$ 个点，可以使用容斥原理解决。
不过 $Lucida$ 跟我讲了另一种做法，统计第一个经过的点是谁的方法数即可，这样显然也是补充不漏的，求解速度还会更快一点。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
long long mod = 59393;
int n, m, k, t;
struct point {
long long x, y;
} p[25];
long long fac[maxn];
long long inv[maxn];
long long f[25][25];
long long g[25][2];
long long h[25];
int read(){
int x;
scanf("%d", &x);
return x;
}
bool cmp(point x, point y){
if(x.x == y.x)return x.y < y.y;
return x.x < y.x;
}
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
b = b * b % mod;
x >>= 1;
}
return ret;
}
long long getc(long long x, long long y){
if(x < y)return 0;
return fac[x] * inv[x - y] % mod * inv[y] % mod;
}
long long lucas(long long x, long long y){
if(y == 0)return 1;
return getc(x % mod, y % mod) * lucas(x / mod, y / mod) % mod;
}
int init(){
fac[0] = 1;
inv[0] = 1;
for(long long i=1;i<mod;i++){
fac[i] = fac[i - 1] * i % mod;
inv[i] = qpow(fac[i], mod - 2);
}
return 0;
}
int main(){
int i, j;
long long l, r;
long long x, y;
long long ans = 0;
init();
n = read();
m = read();
k = read();
for(i=0;i<k;i++){
p[i].x = read();
p[i].y = read();
}
sort(p, p + k, cmp);
for(i=0;i<k;i++){
for(j=i+1;j<k;j++){
if(p[i].y > p[j].y)continue;
l = p[j].x - p[i].x;
r = p[j].y - p[i].y;
for(x=0;x<=min(l,r);x++){
f[i][j] = (f[i][j] + lucas(l + r - 2 * x, l - x) * lucas(l + r - x, x) % mod) % mod;
}
}
}
for(i=0;i<k;i++){
l = p[i].x - 1;
r = p[i].y - 1;
for(x=0;x<=min(l,r);x++){
g[i][0] = (g[i][0] + lucas(l + r - 2 * x, l - x) * lucas(l + r - x, x) % mod) % mod;
}
l = n - p[i].x + 1;
r = m - p[i].y + 1;
for(x=0;x<=min(l,r);x++){
g[i][1] = (g[i][1] + lucas(l + r - 2 * x, l - x) * lucas(l + r - x, x) % mod) % mod;
}
}
l = n;
r = m;
for(x=0;x<=min(l,r);x++){
ans = (ans + lucas(l + r - 2 * x, l - x) * lucas(l + r - x, x) % mod) % mod;
}
/*第二种做法*/
for(i=0;i<k;i++){
h[i] = g[i][0];
for(j=0;j<k;j++){
h[i] -= h[j] * f[j][i] % mod;
h[i] %= mod;
}
ans -= h[i] * g[i][1] % mod;
ans %= mod;
}
/*容斥做法*/
/*for(i=1;i<(1<<k);i++){
x = -1;
long long tmp = 1;
int cnt = 0;
for(j=0;j<k;j++){
if((i >> j) & 1){
cnt++;
if(x == -1){
tmp = (tmp * g[j][0]) % mod;
}else{
tmp = (tmp * f[x][j]) % mod;
}
x = j;
}
}
tmp = (tmp * g[x][1]) % mod;
ans += (cnt % 2 == 0 ? 1ll : -1ll) * tmp;
ans %= mod;
}*/
ans = (ans % mod + mod) % mod;
printf("%lld\n", ans);
return 0;
}