双倍经验 CF559C
前置知识：网格图内任意两点间的路径数量。这个我们可以通过组合数的方法计算出来。假设我们从点 \((1,1)\) 走到点 \((i,j)\)，在这个过程中我们的移动步数是 \(|i-1+j-1|=|i+j-2|\)，其中有 \(|i-1|\) 步需要向下走，那么路径数量即为 \(\binom{i-1}{i+j-2}\)。
然后我们就可以开始做这道题了。这题显然没有什么直接计算答案的方法，所以考虑正难则反。我们计算出到 \((h,w)\) 的所有不合法路径，再用总路径减去这个不合法路径数量即可。那么不合法路径数量怎么算呢？注意到从原点到 \((x,y)\) 的路径数量是可以直接计算的，我们可以考虑对每个不能走的点计算出从原点到它的路径数量。根据乘法原理，我们可以计算出从不合法点 \((x,y)\) 到终点 \((h,w)\) 的路径数量，再乘上从原点到 \((x,y)\) 的路径数量，这样即为经过这个点的不合法路径数量。但这样显然会算重。这里我们只需枚举每个不合法点 \(i\) 的左上方的不合法点 \(j\)，利用乘法原理将 \(i\) 的答案减去 \(i \rightarrow j\) 的路径数量即可。时间复杂度 \(O(n^2)\)。这里由于我代码里没有预处理阶乘逆元所以复杂度应该还有一个 \(logn\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e5+10;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
int h,w,n;
struct node{
int x,y;
bool operator <(const node &a)const{
if(x==a.x) return y<a.y;
return x<a.x;
}
}a[3010];
int f[N];
int fac[N*2];
int quickpow(int x,int p){
int ans=1;
while(p){
if(p&1) ans=ans*x%mod;
x=x*x%mod;
p>>=1;
}
return ans;
}
void init(){
fac[0]=1;
for(int i=1;i<=N*2+10;i++){
fac[i]=fac[i-1]*i%mod;
}
}
int C(int n,int m){
return fac[n]*quickpow(fac[m],mod-2)%mod*quickpow(fac[n-m],mod-2)%mod;
}
signed main(){
h=read();
w=read();
n=read();
init();
for(int i=1;i<=n;i++){
a[i].x=read();
a[i].y=read();
}
a[++n].x=h,a[n].y=w;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
f[i]=C(a[i].x+a[i].y-2,a[i].x-1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j].x<=a[i].x&&a[j].y<=a[i].y){
f[i]-=f[j]*C(a[i].x-a[j].x+1+a[i].y-a[j].y+1-2,a[i].x-a[j].x+1-1);
f[i]=(f[i]+mod)%mod;
}
}
}
cout<<(f[n]+mod)%mod<<endl;
return 0;
}