题目链接:
题目大意:
给出一个h*r的矩阵,从左上角走到右下角,中间有一些点不能经过,问不同的路径有多少种?
题目分析:
- 首先我们考虑一个n*m的矩阵,从左上角只能向右或向下走能走到右下角的方案数,也就是C(n+m,n),就是一共要走n+m次,选出n次横着走。
- 那么我们定义dp[i]表示在前不经过黑块的情况下到达第i个黑块的方案数。
- dp[i]=Cxixi+yj−∑xj<=xiandyj<=yidp[j]⋅Cxi−xjxi+yi−xj−yj
- 相当于是每次统计之前没有雷的情况到达当前点的情况数,再减去到达每个雷的情况*以每个雷为起点到达第i个雷的情况数,利用求补集的方法进行求解。
- 只需要将右下角的点当作一个雷,直接按照转移方程转移即可。
AC代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 200007
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
LL f[MAX];
LL dp[MAX];
int h,w,n;
struct Node
{
int x,y;
bool operator < ( const Node & a ) const
{
return x+y < a.x+a.y;
}
}p[MAX];
LL inv ( LL num , LL n )
{
LL ret = 1;
while ( n )
{
if ( n&1 )
{
ret *= num;
ret %= mod;
}
num *= num;
num %= mod;
n >>= 1;
}
return ret;
}
void init ( )
{
f[0] = 1 , f[1] = 1;
for ( int i = 2 ; i < MAX ; i++ )
f[i] = f[i-1]*i%mod;
}
LL C ( int i , int j )
{
return f[i]*inv( f[j]*f[i-j]%mod , mod-2 )%mod;
}
int main ( )
{
init ( );
while ( ~scanf ("%d%d%d" , &h , &w , &n ) )
{
for ( int i = 0 ; i < n ; i++ )
{
scanf ("%d%d" , &p[i].x , &p[i].y );
p[i].x--;p[i].y--;
}
p[n].x = h-1 , p[n].y = w-1;
sort ( p , p+n+1 );
memset ( dp , 0 , sizeof ( dp ));
for ( int i = 0; i <= n ; i++ )
{
int x = p[i].x , y = p[i].y;
dp[i] = C ( x+y , x );
for ( int j = 0 ; j < i ; j++ )
{
int u = p[j].x , v = p[j].y;
if ( u > x || v > y ) continue;
dp[i] -= C( x-u+y-v , x-u )*dp[j]%mod;
dp[i] = (dp[i]%mod+mod)%mod;
}
//cout << i << " : " << dp[i] << endl;
}
printf ( "%I64d\n" , dp[n] );
}
}