51nod 1486 大大走格子(容斥原理)

1486 大大走格子

題目來源： CodeForces

基準時間限制：1 秒 空間限制：131072 KB 分值: 160 難度：6級算法題  

有一個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取餘的結果。      

Input示例

3 4 2
2 2
2 3      

Output示例

2      

/*
51nod 1486 大大走格子(容斥原理)

problem:
有一個h行w列的棋盤，裡面有一些格子是不能走的，現在要求從左上角走到右下角的方案數。隻能往右 或者 往下

solve:
很明顯用所有的方案數減去經過黑點的方案數就是答案. 而有的重複計算,是以容斥一下.
然後就沒什麼想法了, 主要是覺得方案數不怎麼好求(結果發現可以直接組合數解決...GG)
容斥計算出每個黑點到左上角的方案數, ans[i] - sum(ans[j] * f(j,i) while j < i) f來表示i,j之間的方案數
是以把h,w加入黑點全部求一遍.

hhh-2016/09/26-21:12:09
*/
#pragma comment(linker,"/STACK:124000000,124000000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <math.h>
#define lson  i<<1
#define rson  i<<1|1
#define ll long long
#define clr(a,b) memset(a,b,sizeof(a))
#define key_val ch[ch[root][1]][0]
using namespace std;
const int maxn = 1e6 + 1000;
const int inf = 0x3f3f3f3f;
const ll mod = 1000000007;
const double eps = 1e-7;
template<class T> void read(T&num)
{
    char CH;
    bool F=false;
    for(CH=getchar(); CH<'0'||CH>'9'; F= CH=='-',CH=getchar());
    for(num=0; CH>='0'&&CH<='9'; num=num*10+CH-'0',CH=getchar());
    F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p)
{
    if(!p)
    {
        puts("0");
        return;
    }
    while(p) stk[++ tp] = p%10, p/=10;
    while(tp) putchar(stk[tp--] + '0');
    putchar('\n');
}

ll pow_mod(ll a,ll n)
{
    ll cnt = 1;
    ll t = a % mod;

    while(n)
    {
        if(n & 1) cnt = cnt * t % mod;
        t = t*t%mod;
        n >>= 1;
    }
    return cnt;
}

int h,w,n;
ll ans[maxn];
ll fac[maxn];
ll inv[maxn];
struct node
{
    int a,b;
}x[maxn];
bool cmp(node u,node v)
{
    if(u.a != v.a)
        return u.a < v.a;
    else
        return u.b < v.b;
}

int main()
{
    read(h),read(w),read(n);
    for(int i = 0;i < n;i++)
    {
        read(x[i].a),read(x[i].b);
    }
    x[n].a = h,x[n].b= w;
//    for(int i = 0;i <= n;i++)
//        cout << x[i].a << " " <<x[i].b <<endl;
    fac[0] = inv[0] = 1;
    fac[1] = 1,inv[1] = 1;
    sort(x , x + n + 1,cmp);
    for(int i = 2;i <= h + w;i++)
    {
        fac[i] = fac[i-1] * i % mod;
        inv[i] = pow_mod(fac[i],mod-2);
    }
    for(int i = 0;i <= n;i++)
    {
        int tx = x[i].a,ty = x[i].b;
        ans[i] = fac[tx + ty-2] * inv[tx-1]%mod * inv[ty-1] % mod;
        for(int j = 0;j < i;j++)
        {
            if(x[j].a <= x[i].a && x[j].b <= x[i].b)
            {
                 int tu = x[j].a,tv = x[j].b;
                 ans[i] = (ans[i] - ans[j]*fac[tx-tu+ty-tv] % mod * inv[tx-tu]%mod*inv[ty-tv]%mod)%mod;
            }

        }
        while(ans[i] < 0)
           ans[i] += mod;
        ans[i] %= mod;
    }
//    for(int i = 0;i < n;i++)
//        print(ans[i]);
    print(ans[n]);
    return 0;
}
           

　　

轉載于:https://www.cnblogs.com/Przz/p/5910729.html