题目大意
给出$N\times M$网格图，其中包含$T$个障碍点，询问从$(0,0)$走到$(n,m)$的最短路径条数，不能经过障碍点。
答案对$p$取模。
$1\le N,M\le 10^{10}\quad 0\le T\le 200\quad p=1000003,1019663265$
题目分析
这道题可以说是这两道题的结合版：怎样学习哲学、古代猪文
如果您还没有学习过哲学，请先参考这里。
如果说没有$p=1019663265$的这一种情况，那就和怎样学习哲学几乎一模一样了，只是将组合数部分从$C_m^n$改成了$C_{n+m}^{m}$。
如果$p=1019663265$，显然$p$不是一个素数，我们需要对其进行分解。
如果您还不会使用CRT解决多项式模非素数问题，请移步这里，然后尝试先做此题。
分解$1019663265$得到$\lbrace 3,5,6793,10007 \rbrace$，分别使用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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
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;
}
namespace Solve1 {
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;
}
}
namespace Solve2 {
const LL mod[]= {0,3,5,6793,10007},Mod=1019663265;
LL F[11005][5],invF[11005][5];
LL Quick_Pow(LL a,LL b,LL mod=Mod) {
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,int id) {
if(m>n)return 0;
return F[n][id]*invF[m][id]%mod[id]*invF[n-m][id]%mod[id];
}
LL Lucas(LL n,LL m,int id) {
if(!m)return 1;
return (C(n%mod[id],m%mod[id],id)*Lucas(n/mod[id],m/mod[id],id))%mod[id];
}
LL inv(LL a,LL mod) {
return Quick_Pow(a,mod-2,mod);
}
LL Crt(const LL* a) {
LL ans=0;
for(int i=1; i<=4; i++) {
LL M=Mod/mod[i];
ans=(ans+M*inv(M,mod[i])*a[i])%Mod;
}
return ans;
}
LL Solve(LL n,LL m) {
LL a[5];
for(int i=1; i<=4; i++)a[i]=Lucas(n,m,i);
return Crt(a);
}
}
LL n,m,p,f[205];
struct Point {
LL x,y;
bool operator < (const Point& b) const {
return x<b.x||(x==b.x&&y<b.y);
}
} a[205];
int main() {
n=Get_Int();
m=Get_Int();
p=Get_Int();
if(Get_Int()==1000003) {
using namespace Solve1;
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);
}
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,a[p+1].y=m;
for(int i=1; i<=p+1; i++) {
f[i]=Lucas(a[i].x+a[i].y,a[i].y);
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].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)%mod)%mod+mod)%mod;
}
printf("%lld\n",f[p+1]);
} else {
using namespace Solve2;
for(int i=1; i<=4; i++) {
F[0][i]=invF[0][i]=1;
for(int j=1; j<=10010; j++) {
F[j][i]=F[j-1][i]*j%mod[i];
invF[j][i]=inv(F[j][i],mod[i]);
}
}
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,a[p+1].y=m;
for(int i=1; i<=p+1; i++) {
f[i]=Solve(a[i].x+a[i].y,a[i].y);
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]*Solve(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)%Mod)%Mod+Mod)%Mod;
}
printf("%lld\n",f[p+1]);
}
return 0;
}
