LG5376 [THUPC2019]过河卒二

· · 题解

其实这个题蛮简单的。

作为一个国家抬杠二级运动员，我们要杠一下这句话：

请注意，上述背景内容与本题无关！

我非要让你有关

考虑普通的过河卒，若没有马（不是骂人），那么从 (0,0)->(n,m)，的方案数是 C_{n+m}^n。其意义是，我总共走 n+m 步，其中 n 步向上，选出这 n 步的位置就是方案数。

现在我们还可以沿着斜对角走，我们枚举斜着走的方案数：

ans=\sum\limits_{i=0}^{\min(n,m)} C_{n+m-i}^i\cdot C_{n+m-2*i}^{n-i}

我们回归题目，题目现在是 (1,1)->(n,m)。题目里说：

其次，过河卒二的终点不再是一个特定的位置，Kiana 规定卒可以从棋盘的上方或右方走出棋盘，此时就视为游戏成功。注意在走出棋盘时仍然有方向选择的不同。

我们可以认为是从 (1,1)->(n+1,m+1) 呀，理解为加上一行一列。

但是现在还有一个疑难没解决，就是障碍的问题。可以用容斥原理来计算。但是时间会炸。可以先预处理。我们对每个障碍按横坐标排序，排序后计算出任意两个之间方案数，带入公式：

ans=\sum\limits_{S} calc(S)\times (-1^{|S|})

由于模数是质数，可以用 Lucas 定理解决。

//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
    char ch=getchar();
    int f=1,x=0;
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

const int MAXN=1e5+10,MOD=59393; 

int n,m,k;
int jc[MAXN],f[21][21],invjc[MAXN];
struct point {
    int x,y;
}p[21];

bool cmp(point a,point b) {
    if(a.x!=b.x) {
        return a.x<b.x;
    }
    return a.y<b.y;
}

int qpow(int x,int y) {
    int ret=1;
    while(y) {
        if(y&1) {
            ret=ret*x%MOD;
        }
        x=x*x%MOD;
        y>>=1;
    }
    return ret;
}
int inv(int x) {
    return qpow(x,MOD-2);
}

int C(int x,int y) {
    if(y>x) {
        return 0;
    }
    return jc[x]*invjc[y]%MOD*invjc[x-y]%MOD;
}

int lucas(int x,int y) {
    if(y==0) {
        return 1;
    }
    return lucas(x/MOD,y/MOD)*C(x%MOD,y%MOD)%MOD;
}

int fff(int n,int m) {
    if(min(n,m)<0) {
        return 0;
    }
    int ret=0,ub=min(n,m);
    for(int i=0;i<=ub;i++) {
        ret=(ret+lucas(n+m-i,i)*lucas(n+m-i*2,n-i)%MOD)%MOD;
    }
    return ret;

}

int calc(int s) {
    if(!(s&(1<<0))||!(s&(1<<k))) {
        return 0;
    }
    int lst[22]={},cnt=0,times=1;
    for(int i=0;i<=k;i++) {
        if(s&(1<<i)) {
            lst[++cnt]=i;
            times=times*-1;
        }
    }
    times=(times+MOD)%MOD;
    for(int i=2;i<=cnt;i++) {
        times=times*f[lst[i-1]][lst[i]]%MOD;
    }
    return times;
}

signed main() {
    jc[0]=1;
    invjc[0]=1;
    for(int i=1;i<=MOD;i++) {
        jc[i]=jc[i-1]*i%MOD;
        invjc[i]=inv(jc[i]);
    }
    cin>>n>>m>>k;
    n++;
    m++;
    for(int i=1;i<=k;i++) {
        p[i].x=read();
        p[i].y=read();
    }
    p[0].x=1;p[0].y=1;
    k++;
    p[k].x=n;
    p[k].y=m;
    sort(p+1,p+k+1,cmp);

    for(int i=0;i<=k;i++) {
        for(int j=i+1;j<=k;j++) {
            f[i][j]=fff(p[j].x-p[i].x,p[j].y-p[i].y);
        }
    }

    int ans=0;
    for(int i=0;i<(1<<k+1);i++) {
        ans=(ans+calc(i))%MOD;
    }
    cout<<ans<<endl;
    return 0;
}