隐藏
「bsoj5045」怎样学习哲学 - 动态规划+组合数学 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj5045」怎样学习哲学 - 动态规划+组合数学

题目大意

有一个$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;
}
姥爷们赏瓶冰阔落吧~