题解：P5376 [THUPC 2019] 过河卒二

· · 题解

题意

卒从 (1,1) 出发，可以向令 x+1，或 y+1，或 x+1 并且 y+1。棋盘上有一些地方不可到达，求到达 (n+1,m+1) 的方案数（原文不是这样的，但是转化之后是的）。

思路

首先考虑没有障碍时怎么做。

设 dp_{i,j} 表示在没有障碍的情况下，到达 (i,j) 的方案数。

如果只有 x+1，y+1 两个操作是好做的，走斜线就比较烦人。

所以考虑枚举走的斜线数量。

直接给出 dp_{i,j} 的计算方法。

dp_{i+1,j+1}=\sum_{k=0}^{\min(i,j)} C_{i+j-k \times 2}^{i-k} \times C_{i+j-k}^{k}

如果有点想不明白，可以先假设斜线是在一起的，再将其与直线混在一起，求出组合数就行了。

接下来加上障碍。

考虑容斥原理（其实挺显然的吧）。

注意到 k 只有 20，考虑暴力枚举经过了哪几个障碍即可。

具体的，先将障碍物按照 x 为第一关键字，y 为第二关键字从小到达排序，预处理出两两之间的方案数（与上文的类似）。

然后状态压缩一下就行了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

const int mod=59393;
namespace Memory_Love{
    int read(){ int x=0; bool flag=1; char ch=getchar();
        while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
        while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
    template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
        while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
        while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
    template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
    template<typename T> void write(T x,char ch=0){if(x<0) x=-x,putchar('-');
        static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
        while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
    int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
    int lcm(int a,int b){return a/gcd(a,b)*b;}
    void MADD(int &x,int y,int mod){x=(x+y>=mod? x+y-mod:x+y);}
    int ksc(int a,int b,int p){int ans=0;while(b){if(b&1)MADD(ans,a,p);MADD(a,a,p);b>>=1;}return ans;}
    int ksm(int a,int b,int p){int ans=1%p;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
    int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return a;}int d=exgcd(b,a%b,y,x);y-=a/b*x;return d;}
    int inv(int t){int x,y;exgcd(t,mod,x,y);return (x%mod+mod)%mod;}
} using namespace Memory_Love;
const int N=1e5+5;
const int MK=22;
int n,m,k;
int B[MK][MK];

namespace FACT
{
    int fact[mod+5],infact[mod+5];
    void init(int n)
    {
        int i;
        for(i=fact[0]=infact[0]=1;i<=n;i++)
        {
            fact[i]=fact[i-1]*i%mod;
            infact[i]=infact[i-1]*ksm(i,mod-2,mod)%mod;
        }
    }
    int C(int n,int m)
    {
        if(n<m) return 0;
        return fact[n]*infact[m]%mod*infact[n-m]%mod;
    }
    int Lucas(int n,int m)
    {
        if(m==0) return 1;
        return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
    }
} using FACT::Lucas;

struct Barrier
{
    int x,y;
}a[MK];
bool comp(const Barrier &a,const Barrier &b)
{
    if(a.x!=b.x)
    return a.x<b.x;
    else 
    return a.y<b.y;
}

int DP(int n,int m)
{
    int i,ans=0; n--,m--;
    for(i=0;i<=min(n,m);i++)
    (ans+=Lucas(n+m-i*2,n-i)*Lucas(n+m-i,i))%=mod;
    return ans;
}

bool Ending;
signed main()
{
    int i,j;
    read(n,m,k);
    FACT::init(mod-1);
    for(i=1;i<=k;i++)
    read(a[i].x,a[i].y);
    sort(a+1,a+1+k,comp);
    a[0]=(Barrier){1,1};
    a[k+1]=(Barrier){n+1,m+1};

    for(i=0;i<=k+1;i++)
    {
        for(j=i+1;j<=k+1;j++)
        {
            if(a[i].y>a[j].y)
            B[i][j]=0;
            else
            B[i][j]=DP(a[j].x-a[i].x+1,a[j].y-a[i].y+1);
        }
    }

    int ans=DP(n+1,m+1);
    for(i=0;i<(1<<k);i++)
    {
        if(i==0) continue;
        int now=1,last=0,t=-1;
        for(j=0;j<k;j++)
        {
            if(i>>j&1)
            {
                (now*=B[last][j+1])%=mod;
                last=j+1;
                t=-t;
            }
        }
        (ans-=now*B[last][k+1]*t)%=mod;
    }
    write((ans%mod+mod)%mod,'\n');
    cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
    return 0;
}