【51nod1486】大大走格子

  • 本文为博主原创,未经许可不得转载

取出 k 个坏格,记 f[i] 表示从左上角不经过其它坏格,走到第 i 个坏格的方案数

考虑转移,走到 (x,y) 这个格,共有 C(x+y, x) 种方案

减掉不合法的,枚举第一次经过的坏格为 j

f[i] -= f[j] * C(x[i]+y[i]-x[j]-y[j], x[i] - x[j])

把终点也视为一个坏格,就能算方案数了

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
#include<bits/stdc++.h>
#define FILE "read"
#define N 200000
using namespace std;
typedef long long ll;
const ll mod=(ll)1e9+7;
struct node{ll x,y;}p[2010];
ll n,m,k,f[2010],inv[N+50],fac[N+50];
inline ll read(){
ll x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
bool cmp(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
ll fast(ll a,ll b){ll ret(1);for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod;return ret;}
ll C(ll n,ll m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
void pre(){
fac[0]=1; for(ll i=1;i<=N;++i) fac[i]=fac[i-1]*i%mod;
inv[N]=fast(fac[N],mod-2);
for(ll i=N-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read()-1; m=read()-1; k=read(); pre();
for(ll i=1;i<=k;++i) p[i].x=read()-1,p[i].y=read()-1;
p[++k].x=n; p[k].y=m;
sort(p+1,p+k+1,cmp);
for(ll i=1;i<=k;++i){
f[i]=C(p[i].x+p[i].y,p[i].x);
for(ll j=1;j<i;++j)
if(p[i].y>=p[j].y) (f[i]-=f[j]*C(p[i].x+p[i].y-p[j].x-p[j].y,p[i].x-p[j].x)%mod)%=mod;
}
printf("%lld\n",(f[k]+mod)%mod);
return 0;
}
文章目录
,