[Codeforces Round #313 (Div. 1) pC][DP] Gerald and Giant Chess

原題連結
本來一直往dp[i][j]=dp[i-1][j]+dp[i][j-1]去想......結果不管怎麼弄都逃離不了O(n^2)XD

最後看了codeforces上的tag寫著combinatorics!


才突然想起高中數學也有教，從(0,0)走到(n,m)的捷徑方法數是C(n+m,m)，這是解這題的其中一個關鍵


再來就是如何制定狀態和狀態轉移了。由於原題是問「走到(h,w)不經過任何黑格的方法數」，不妨將dp[i]定為「走到第i個黑格並且不經過任何黑格的方法數」，然後將(h,w)變成第n+1個黑格
便可以遞推求解。

那要怎麼轉移呢？首先，會影響到第i個黑格的狀態顯然是那些x,y座標都比第i個黑格小的那些黑格，在考慮轉移順序時要先注意到這件事情。接著，由於直接算出dp[i]相當困難，我們考慮反面作法，用「從(0,0)走到(r_i,c_i)的方法數」-「從(0,0)走到(r_i,c_i)且至少經過1黑格的方法數」，可以發現其實就是所有dp[j] , (r_j<=r_i && c_j<=c_i)去乘上從(r_j,c_j)到(r_i,c_i)的方法數。如果覺得難以理解，可以重新想想狀態表示。

#define LL long long
#include<bits/stdc++.h>
using namespace std;
const LL maxn=2000+5;
const LL maxh=200000+5;
const LL MOD=1000000000+7;
struct Cell
{
    LL r,c;
    bool operator < (const Cell& rhs) const {return r<rhs.r || (r==rhs.r && c<rhs.c);}
}cell[maxn];
void extgcd(LL a,LL& x,LL b,LL& y,LL& d)
{
    if(b==0) {x=1,y=0,d=a;}
    else {extgcd(b,y,(a%b),x,d);y-=x*(a/b);}
}
LL inv(LL a,LL mod) // ax = 1 mod (mod) --> ax - mod*y = 1
{
    LL x,y,d;
    extgcd(a,x,mod,y,d);
    assert(d==1);
    return ((x%MOD)+MOD)%MOD;
}
LL fac[maxh];
LL C(LL n,LL m)
{
    assert(n>=m);
    return (((fac[n]*inv(fac[m],MOD))%MOD)*inv(fac[n-m],MOD))%MOD;
}
LL dp[maxn];
main()
{
    fac[0]=1;
    for(LL i=1;i<maxh;i++) fac[i]=(fac[i-1]*i)%MOD;
    LL h,w,n;
    scanf("%I64d%I64d%I64d",&h,&w,&n);
    cell[n].r=h-1,cell[n].c=w-1;
    for(LL i=0;i<n;i++) {scanf("%I64d%I64d",&cell[i].r,&cell[i].c);cell[i].r--;cell[i].c--;}
    sort(cell,cell+n);
    for(LL i=0;i<=n;i++)
    {
        dp[i]=C(cell[i].r+cell[i].c,cell[i].c);
        for(LL j=0;j<i;j++) if(cell[i].r>=cell[j].r && cell[i].c>=cell[j].c)
            dp[i]=(((dp[i]-(dp[j]*C(cell[i].r-cell[j].r+cell[i].c-cell[j].c,cell[i].r-cell[j].r))%MOD)%MOD)+MOD)%MOD;
    }
    printf("%I64d\n",dp[n]);
}