CFR 559 C. Gerald and Giant Chess ( DP )

Problem - C - Codeforces

題意：
在一個棋盤上，起點 ( 1, 1 ) 終點 ( H, W )，給若干個禁止點，求不走遠路的路徑數，不經過禁止點，其餘數。

資料規模：
1 ≤ H, W ≤ 1e5
禁止點數 1 ≤ N ≤ 2000

解法：
預處理階乘表後，可以用組合公式 ( H + W ) ! / ( H ! * W! )，分母用尤拉定理和快速冪，在 O( lg( MOD ) ) 時間內求出 ( 1, 1 ) 至 ( H, W ) 的不走遠路路徑數。接著對禁止點們按照 x ，平手則 y 的優先性進行排序，目的是讓後面的禁止點不影響前面的，這樣較容易定義動態規劃。
dp[ i ] : ( 1, 1 ) 走至第 i 個禁止點，且無其他造訪的禁止點，這樣的路徑數
dp[ i ] = { ( 1, 1 ) 走至 第 i 個禁止點的不走遠路路徑數 } - SIGMA{ dp[ j ] * { 第 j 個禁止點 走至 第 i 個禁止點的不走遠路路徑數 } | j < i }
答案就會是 { ( 1, 1 ) 走至 ( H, W ) 的不走遠路路徑數 } - SIGMA{ dp[ i ] * { 第 i 個禁止點 走至 ( H, W ) 的不走遠路路徑數 } | for all i }

時間 / 空間複雜度：
O( N ^ 2 lg( MOD ) ) / O( N ^ 2 )

vi fact; // preprocessed factorial
vi dp; // how many ways to be here as the first blocking

int ways( int h, int w ){ // how many shortest paths to go from ( 0, 0 ) to ( h, w )
    function< int ( int, int ) > fp = [ & ]( int x, int p ){
        int res = 1;
        while( p ){
            if( p & 1 ) res = 1LL * res * x % MOD7;
            p >>= 1, x = 1LL * x * x % MOD7;
        }
        return res;
    };
    function< int ( int ) > inv = [ & ]( int x ){ return fp( x, MOD7 - 2 ); };
    return 1LL * fact[ h + w ] * inv( 1LL * fact[ h ] * fact[ w ] % MOD7 ) % MOD7;
}

void preprocess(){
    fact = vi( ( int ) 2e5 + 1 );
    for( int i = fact[ 0 ] = 1; i < fact.size(); ++i )
        fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD7;
    sort( A.begin(), A.end() );
    dp = vi( N );
    for( int i = 0; i < N; ++i ){
        dp[ i ] = ways( A[ i ].first - 1, A[ i ].second - 1 );
        for( int j = 0; j < i; ++j )
            if( A[ j ].first <= A[ i ].first and A[ j ].second <= A[ i ].second )
                ( dp[ i ] -= 1LL * dp[ j ] * ways( A[ i ].first - A[ j ].first, A[ i ].second - A[ j ].second ) % MOD7 ) %= MOD7;
    }
}

void solve(){
    int ans = ways( H - 1, W - 1 );
    for( int i = 0; i < N; ++i )
        ( ans -= 1LL * dp[ i ] * ways( H - A[ i ].first, W - A[ i ].second ) % MOD7 ) %= MOD7;
    cout << ( ans + MOD7 ) % MOD7 << endl;
}