codeforces 559C Gerald and Giant Chess(dp+組合數學)

題目連結：

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代碼：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 200007

using namespace std;

typedef long long LL;

const LL mod = +;

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 = ;
    while ( n )
    {
        if ( n& )
        {
            ret *= num;
            ret %= mod;
        }
        num *= num;
        num %= mod;
        n >>= ;
    }
    return ret;
}

void init ( )
{
    f[] =  , f[] = ;
    for ( int i =  ; i < MAX ; i++ )
        f[i] = f[i-]*i%mod;
}

LL C ( int i , int j )
{
    return f[i]*inv( f[j]*f[i-j]%mod , mod- )%mod;
}

int main ( )
{
    init ( );
    while ( ~scanf ("%d%d%d" , &h , &w , &n ) )
    {
        for ( int i =  ; i < n ; i++ )
        {
            scanf ("%d%d" , &p[i].x , &p[i].y );
            p[i].x--;p[i].y--;
        }
        p[n].x = h- , p[n].y = w-;
        sort ( p , p+n+ );
        memset ( dp ,  , sizeof ( dp ));
        for ( int i = ; i <= n ; i++ )
        {
            int x = p[i].x , y = p[i].y;
            dp[i] = C ( x+y , x );
            for ( int j =  ; 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] );
    }
}