以后都懒得写题目大意和数据范围了。
hz学长的题其实也不那么毒瘤吗。比CDW的好多了
先考虑没有障碍怎么做。
首先发现，答案相当于一个左下角是 $(1,1)$，右上角是 $(n+1,m+1)$ 的棋盘，从 $(1,1)$ 走到 $(n+1,m+1)$ 的方案数。因为走到最上或最右就只有一种选法了。
枚举斜着走的次数 $i$。答案是 $sumlimits_{i=0}^{min(n,m)}dbinom{n+m-i}{i}dbinom{n+m-2i}{n-i}$。前面是选哪几步，后面是经典过河卒。（注意 $n,m$ 是 $x2-x1$ 和 $y2-y1$）
现在考虑有障碍。明显容斥。
令 $g[S]$ 表示至少经过 $S$ 中障碍的方案数。（可能经过更多的障碍）
答案是 $sumlimits_Sg[S](-1)^{|S|}$。
如何计算 $g[S]$？
先把障碍按 $x$ 为第一关键字排序，按 $y$ 为第二关键字排序。
那么 $S$ 中如果存在 $i<j,y[i]>y[j]$ 那么为 $0$。
否则就是从起点到第一个点的方案数，从第一个点到第二个点的方案数……从最后一个点到终点的方案数的乘积。
时间复杂度看起来是 $O(2^kmin(n,m))$。
但是我们发现很多个方案数是被重复计算的。如果我们预处理两两点之间的方案数就能做到 $O(2^kk+k^2min(n,m))$。
模数是质数，可以用卢卡斯定理。
#include<bits/stdc++.h> using namespace std; const int mod=59393; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ char ch=getchar();int x=0,f=0; while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } struct pos{ int x,y; bool operator<(const pos &p)const{ if(x!=p.x) return x<p.x; return y<p.y; } }p[22]; int n,m,k,x[22],y[22],cnt[22][22],fac[mod],inv[mod],invfac[mod],ans,sz[1111111],in[22],out[22]; void init(){ fac[0]=fac[1]=inv[1]=invfac[0]=invfac[1]=1; FOR(i,2,mod-1){ fac[i]=1ll*fac[i-1]*i%mod; inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod; invfac[i]=1ll*invfac[i-1]*inv[i]%mod; } } int C(int n,int m){ if(n<0 || m<0 || n<m) return 0; return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod; } int lucas(int n,int m){ if(n<mod) return C(n,m); return 1ll*lucas(n/mod,m/mod)*lucas(n%mod,m%mod)%mod; } int calc(int n,int m){ int ans=0; FOR(i,0,min(n,m)) ans=(ans+1ll*lucas(n+m-i,i)*lucas(n+m-2*i,n-i))%mod; return ans; } int solve(int S){ int pre=-1,ans=1; FOR(i,0,k-1) if((S>>i)&1){ if(pre==-1) ans=1ll*ans*in[i]%mod; else{ if(y[pre]>y[i]) return 0; ans=1ll*ans*cnt[pre][i]%mod; } pre=i; } if(~pre) return 1ll*ans*out[pre]%mod; else return calc(n,m); } int main(){ n=read();m=read();k=read(); init(); FOR(i,0,k-1) p[i].x=read(),p[i].y=read(); sort(p,p+k); FOR(i,0,k-1) x[i]=p[i].x,y[i]=p[i].y; FOR(i,0,k-1) FOR(j,i+1,k-1) cnt[i][j]=calc(x[j]-x[i],y[j]-y[i]); FOR(i,0,k-1) in[i]=calc(x[i]-1,y[i]-1),out[i]=calc(n+1-x[i],m+1-y[i]); FOR(i,1,(1<<k)-1) sz[i]=sz[i>>1]+(i&1); FOR(i,0,(1<<k)-1){ if(sz[i]&1) ans=(ans-solve(i)+mod)%mod; else ans=(ans+solve(i))%mod; } printf("%d ",ans); }