#计数类dp#洛谷 CF559C Gerald and Giant Chess

题目

有一些格子不可以走，问从棋盘的左上角走到右下角有多少种走法

分析

可以走的格子太多了，所以应该用反向思维，如果都可以走，最终答案为 C r + c − 2 r − 1 C_{r+c-2}^{r-1} Cr+c−2r−1​，然而剩下的？那么可以设 f [ i ] f[i] f[i]为经过第i个不可以走的格子，而没有走过其它不可以走的格子的走法（设终点也是不可以走的格子）

f [ i ] = C x i + y i − 2 x i − 1 − ∑ j = 0 i − 1 f [ j ] × C x i − x j + y i − y j x i − x j ( x i ≥ x j ， y i > y j ) f[i]=C_{x_i+y_i-2}^{x_i-1}-\sum_{j=0}^{i-1}f[j]\times C_{x_i-x_j+y_i-y_j}^{x_i-x_j}(x_i\geq x_j，y_i>y_j) f[i]=Cxi​+yi​−2xi​−1​−j=0∑i−1​f[j]×Cxi​−xj​+yi​−yj​xi​−xj​​(xi​≥xj​，yi​>yj​)

代码

#include <cstdio>
#include <algorithm>
#define p first
#define q second
#define mod 1000000007
typedef long long ll;
std::pair<int,int>x[3001]; ll mul[200001],inv[200001];
int f[3001],a,b,n;
int in(){
    int ans=0; char c=getchar();
    while (c<48||c>57) c=getchar();
    while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
    return ans;
}
ll ksm(ll x,ll y){
    ll ans=1;
    while (y){
        if (y&1) ans=ans*x%mod;
        x=x*x%mod; y>>=1;
    }
    return ans;
}
int c(int n,int m){return mul[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){
    a=in(); b=in(); n=in(); mul[0]=inv[0]=1;
    for (register int i=1;i<=a+b;i++){
        mul[i]=mul[i-1]*i%mod;//阶乘
        inv[i]=ksm(mul[i],mod-2);//逆元(费马小定理)
    }
    for (register int i=0;i<n;i++) x[i].p=in(),x[i].q=in();
    std::stable_sort(x,x+n); x[n].p=a; x[n].q=b;//终点也当作不可以走的格子（目的是为了到达终点）
    for (register int i=0;i<=n;i++){
        f[i]=c(x[i].p+x[i].q-2,x[i].p-1);
        for (register int j=0;j<i;j++){
            if (x[j].p>x[i].p||x[j].q>x[i].q) continue;//避免重复
            f[i]=(f[i]-(ll)f[j]*c(x[i].p+x[i].q-x[j].p-x[j].q,x[i].p-x[j].p))%mod;//减去不合法的方案
        }
    }
    return !printf("%d",(f[n]+mod)%mod);//可能出现负数
}