题意:n行m列的棋盘,其中有k个点无法行走,求从从(0,0)到(n,m)有多少路径。
思路:从(0,0)到(i,j)有C(i+j,j)条路(没有被淹的点),经过(i,j)点的道路数有(C(i+j,j)*C(n-i+m-j,m-j))条,其中要扣去经过被淹点的路。
贴代码:
<span style="font-size:18px;">#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int mod=1000000007;
const int maxn=200055;
int n,m,k,lim;
ll fac[maxn],inv[maxn];
struct data{
int x,y;
ll z;
}a[3003];
inline ll Pow(ll aa,int b){
ll tmp=aa,ret=1;
while(b){
if(b&1)ret=ret*tmp%mod;
tmp=tmp*tmp%mod;
b>>=1;
}
return ret;
}
inline ll C(int x,int y){
if(x==y || y==0)return 1;
return(fac[x]*inv[x-y]%mod*inv[y]%mod); //用逆元求组合数
}
inline int get(){
char c;while(!isdigit(c=getchar()));
int v=c-48;while(isdigit(c=getchar()))v=v*10+c-48;
return v;
}
inline bool cmp(const data&aa,const data&bb){return(aa.x<bb.x ||(aa.x==bb.x && aa.y<bb.y));}
int main(){
n=get(),m=get();k=get();
fac[0]=0;fac[1]=1;
for(int i=2;i<=n+m;++i)fac[i]=fac[i-1]*i%mod;
inv[n+m]=Pow(fac[n+m],mod-2);
for(int i=n+m-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%mod; //O(n)求逆元!
for(int i=1;i<=k;++i)a[i].x=get(),a[i].y=get(),a[i].z=C(a[i].x+a[i].y,a[i].y);
sort(a+1,a+1+k,cmp);
a[++k].x=n,a[k].y=m,a[k].z=C(a[k].x+a[k].y,a[k].y);
for(int i=1;i<k;++i){
for(int j=i+1;j<=k;++j)if(a[i].y<=a[j].y){
a[j].z=(a[j].z+mod-(a[i].z*C(a[j].x-a[i].x+a[j].y-a[i].y,a[j].y-a[i].y))%mod)%mod; //减去经过被淹的点的路径
}
}
printf("%lld\n",a[k].z);
return 0;
}</span>