有一个 h 行 w 列的棋盘, 里面有一些格子是不能走的, 现在要求从左上角走到右下角的方案数.
Input
单组测试数据.
第一行有三个整数 h, w, n(1 h, w 10^5, 1 n 2000), 表示棋盘的行和列, 还有不能走的格子的数目.
接下来 n 行描述格子, 第 i 行有两个整数 ri, ci (1 ri h, 1 ci w), 表示格子所在的行和列.
输入保证起点和终点不会有不能走的格子.
Output
输出答案对 1000000007 取余的结果.
- Sample Input
- 3 4 2 2 2 2 3
- Sample Output
- 2
题目链接
分析
从左上角 (1,1) 走到 (x,y) 的方案数为 C(x-1+y-1,x-1). 设 d[i]为到达第 i 个黑点且中间不经过任何黑点的方案数. 则有 d[i]=C(xi+yi-2,xi-1)-
d[j]*C(xi+yi-xj-yj,xi-yi)(xj<xi,yj<yi). 然后令第 n+1 个黑点为(h,w), 答案即为 d[n+1]. 为什么这样是正确的呢?
对于一个黑点, 可能可以由另外的黑点到达. 实际上枚举时总是从第一个能经过的黑点出发, 每个黑点会对目的黑点的值有影响,
贡献为该黑点的值乘上从该黑点走到目的黑点的方案数.(因为只要经过黑点就是非法的, 所以后面没有限制, 直接走就好了)
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <cstring>
- #include <algorithm>
- #include <map>
- #include <vector>
- typedef long long LL;
- const int maxn = 2e5+5;
- const int inf = 0x3f3f3f3f;
- const int mod = 1000000007;
- using namespace std;
- LL fact[maxn],inv[maxn];
- struct node{
- int x,y;
- }p[2020];
- LL _inv(int x){
- if(x==1) return 1;
- return (mod-mod/x)*_inv(mod%x)%mod;
- }
- void init(){
- fact[0]=1;
- for(int i=1;i<maxn;i++){
- fact[i]=(fact[i-1]*i)%mod;
- }
- for(int i=0;i<maxn;i++){
- inv[i]=_inv(fact[i]);
- }
- }
- LL C(int a,int b){
- if(a<b) return 0;
- return ((fact[a]*inv[b])%mod*inv[a-b])%mod;
- }
- int cmp(node a,node b){
- if(a.x==b.x) return a.y<b.y;
- return a.x<b.x;
- }
- LL d[2020];
- int main(){
- #ifdef LOCAL
- freopen("in.txt","r",stdin);
- #endif
- init();
- int h,w,n;
- scanf("%d%d%d",&h,&w,&n);
- for(int i=0;i<n;i++)
- scanf("%d%d",&p[i].x,&p[i].y);
- sort(p,p+n,cmp);
- p[n].x=h,p[n].y=w;
- n++;
- for(int i=0;i<n;i++){
- d[i]=C(p[i].x+p[i].y-2,p[i].x-1);
- for(int j=0;j<i;j++){
- if(p[i].y>=p[j].y&&p[i].x>=p[j].x){
- d[i] -= (d[j]*C(p[i].x+p[i].y-p[j].x-p[j].y,p[i].x-p[j].x))%mod;
- if(d[i]<0){
- d[i]+=mod;
- }
- }
- }
- }
- cout<<d[n-1];
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2548943.html