codeforces 559 C Gerald and Giant Chess(dp+組合せ数学)
4592 ワード
タイトルリンク:
codeforces 559C
テーマ:
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コード:
codeforces 559C
テーマ:
h*rの行列を与えて、左上の角から右下の角まで歩いて、中間はいくつかの点が通ることができなくて、異なる経路に何種類がありますか?
テーマ分析:
dp[i]=Cxixi+yj−∑xj<=xiandyj<=yidp[j]⋅Cxi−xjxi+yi−xj−yj
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
" , dp[n] );
}
}