题目大意
有一个$n\times m$的矩阵，有一些点不能经过，现在从第一行开始每一行选一个点，下一行选的点必须比上一行靠右，问不经过障碍点的方案数。
题目吐槽
暴力膜蛤不可取，膜蛤不当必被续。
题目分析
首先对于这一类取模的题目，一般有两种思路：组合数学，动态规划。
对于这道题若使用动态规划计数，必须将矩阵设入状态，显然不可行，因此考虑组合数学解决问题。
我们先考虑矩阵中不包含障碍点的情况，我们可以得出以下方案数：
将矩阵的值计算出来：
有没有发现，这是一个倒过来的杨辉三角！
因此对于一个$n\times m$的无障碍点矩阵，其方案数为$C_m^n$。
再考虑如何计算有障碍点的方案数，可以采用容斥原理，在这里我们可以使用动态规划来实现。
设$f[i]$为只经过$i$号障碍点的方案数，这样设状态是因为若包含其它障碍点可能会重复计算，非常麻烦。
转移方程的意思就是：到达$i$障碍点的所有方案减去所有经过了其左上方所有障碍点然后到达$i$点的方案。
最后答案的计算方法为：
因为可以在最后一行任意位置结束，因此可以在$(n+1,m+1)$添加一个障碍点，最后的方案数就是$f[k+1]$
因为组合数很大，因此需要使用Lucas定理计算。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL mod=1000003;
LL F[mod+2],invF[mod+2];
LL Quick_Pow(LL a,LL b) {
LL ans=1;
while(b) {
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
LL C(LL n,LL m) {
if(m>n)return 0;
return F[n]*invF[m]%mod*invF[n-m]%mod;
}
LL Lucas(LL n,LL m) {
if(!m)return 1;
return (C(n%mod,m%mod)*Lucas(n/mod,m/mod))%mod;
}
struct Point {
LL x,y;
bool operator < (const Point& b) const {
return x<b.x||(x==b.x&&y<b.y);
}
} a[2005];
LL n,m,p,f[2005];
int main() {
F[0]=invF[0]=1;
for(int i=1; i<=mod; i++) {
F[i]=F[i-1]*i%mod;
invF[i]=Quick_Pow(F[i],mod-2);
}
n=Get_Int();
m=Get_Int();
p=Get_Int();
for(int i=1; i<=p; i++) {
a[i].x=Get_Int();
a[i].y=Get_Int();
}
sort(a+1,a+p+1);
a[p+1].x=n+1,a[p+1].y=m+1;
for(int i=1; i<=p+1; i++) {
f[i]=Lucas(a[i].y-1,a[i].x-1);
for(int j=1; j<i; j++)
if(a[j].x<a[i].x&&a[j].y<a[i].y)f[i]=((f[i]-f[j]*Lucas(a[i].y-a[j].y-1,a[i].x-a[j].x-1)%mod)%mod+mod)%mod;
}
printf("%lld\n",f[p+1]);
return 0;
}
|
