M_sea

洛谷5376 [THUPC2019]过河卒二
LuoguLOJ分析考虑没有障碍的情况。首先可以发现,答案相当于从 $(1,1)$ 走到 $(n+1,m+1)$ ...
扫描右侧二维码阅读全文
16
2019/07

洛谷5376 [THUPC2019]过河卒二

Luogu

LOJ

分析

考虑没有障碍的情况。

首先可以发现,答案相当于从 $(1,1)$ 走到 $(n+1,m+1)$ 的方案数。

考虑枚举斜着走的次数,可以得到答案为

$$ \displaystyle\sum_{i=0}^{\min\left\{n,m\right\}}\binom{n+m-i}{i}\binom{n+m-2i}{n-i} $$

这个东西也可以理解为 $(x,y)$ 走到 $(x+n,y+m)$ 的方案数。

注意到模数是质数,直接用 Lucas 定理计算组合数即可。

现在有了障碍并且障碍数很小,考虑容斥掉所有经过了障碍的情况。

设 $f_S$ 表示至少经过了 $S$ 中的障碍的方案数,显然答案为 $\displaystyle\sum_{S}(-1)^{|S|}f_S$ 。

考虑如何计算 $f_S$ 。我们先把所有障碍以 $x$ 为第一关键字、$y$ 为第二关键字排序。

如果 $S$ 中存在一对障碍 $(i,j)$ 使得 $x_i<x_j,y_i>y_j$ ,那么方案数为 $0$ ;否则方案数为起点到第一个障碍、第一个障碍到第二个障碍、……、最后一个障碍到终点的方案数的乘积。

直接算时间复杂度比较大,可以预处理出两两障碍之间的方案数。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int K=20+10;
const int mod=59393;

int n,m,k;
int in[K],out[K],cnt[K][K];
int fac[mod],ifac[mod];

struct Point { int x,y; } p[K];
bool operator <(Point a,Point b) {
    if (a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

inline void init() {
    fac[0]=1;
    for (re int i=1;i<mod;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[mod-1]=qpow(fac[mod-1],mod-2);
    for (re int i=mod-1;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}

inline int C(int n,int m) {
    if (n<m) return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

inline int lucas(int n,int m) {
    if (!m) return 1;
    return 1ll*lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}

inline int calc(int n,int m) {
    int res=0;
    for (re int i=0;i<=min(n,m);++i)
        res=(res+1ll*lucas(n+m-i,i)*lucas(n+m-i-i,n-i))%mod;
    return res;
}

inline int solve(int S) {
    if (!__builtin_popcount(S)) return calc(n,m);
    int lst=0,res=1;
    for (re int i=1;i<=k;++i) {
        if ((S&(1<<(i-1)))==0) continue;
        if (!lst) res=1ll*res*in[i]%mod;
        else {
            if (p[i].y<p[lst].y) return 0;
            res=1ll*res*cnt[lst][i]%mod;
        }
        lst=i;
    }
    res=1ll*res*out[lst]%mod;
    return res;
}

int main() {
    n=read(),m=read(),k=read(); init();
    for (re int i=1;i<=k;++i) p[i].x=read(),p[i].y=read();
    sort(p+1,p+k+1);
    for (re int i=1;i<=k;++i) in[i]=calc(p[i].x-1,p[i].y-1);
    for (re int i=1;i<=k;++i) out[i]=calc(n+1-p[i].x,m+1-p[i].y);
    for (re int i=1;i<=k;++i)
        for (re int j=i+1;j<=k;++j)
            cnt[i][j]=calc(p[j].x-p[i].x,p[j].y-p[i].y);
    int ans=0;
    for (re int i=0;i<(1<<k);++i) {
        int now=solve(i);
        if (__builtin_popcount(i)&1) now=mod-now;
        ans=(ans+now)%mod;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 07 月 16 日 08 : 10 PM

发表评论