C++14(g++5.4) 解法, 执行用时: 1421ms, 内存消耗: 8336K, 提交时间: 2020-02-19 18:17:25

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int M = 50;
const int mod = 1e9 + 7;

int fpow (int a, int b) { int ret = 1; while (b) { if (b & 1) ret = 1ll * ret * a % mod; a = 1ll * a * a % mod; b >>= 1; } return ret; }
int add (int a, int b) { return (a += b) >= mod ? a - mod : a; }
int sub (int a, int b) { return (a -= b) >= 0 ? a : a + mod; }
int mul (long long a, int b) { return a * b % mod; }

int f[N], invf[N];

void predeal (int n = N - 1) {
	f[0] = 1;
	for (int i = 1; i <= n; i++) 
		f[i] = mul(f[i - 1], i);
	invf[n] = fpow(f[n], mod - 2);
	for (int i = n - 1; i >= 0; i--) 
		invf[i] = mul(invf[i + 1], i + 1);
}

int bi (int a, int b) { return (a >= b) ? 1ll * f[a] * invf[b] % mod * invf[a - b] % mod : 0; }


// 一点从 (0, 0) 到 (n, m) 每次可以移动 { (1, 0), (0, 1) } 且需要满足 (x, y) : x + k1 < y && y < x + k2

int ff (int n, int m, int k1, int k2) {
	int ret = bi(n + m, n), d[2] = { k1, - k2 };
	for (int x = n + d[0], t = 0; x >= 0 && x <= n + m; x += d[t ^= 1])
		ret = (t ? add(ret, bi(n + m, x)) : sub(ret, bi(n + m, x)));
	for (int x = m + d[1], t = 1; x >= 0 && x <= n + m; x += d[t ^= 1])
		ret = (t ? sub(ret, bi(n + m, x)) : add(ret, bi(n + m, x)));
	return ret;
}

struct Pt { int x, y, col; } a[M];
int dp[M];

int main (void) {
	predeal();

	int kase, kas = 0;
	scanf("%d", &kase);
	while (kase --) {
		int n, m, s, k;
		scanf("%d%d%d%d", &n, &m, &s, &k);
		int k1 = - 1;
		int k2 = m - n + 1;
		for (int i = 1; i <= s + k; i ++)
			scanf("%d%d", &a[i].x, &a[i].y);
		for (int i = 1; i <= s + k; i ++)
			a[i].col = (i <= s);
		sort(a + 1, a + s + k + 1, [](Pt x, Pt y){
			return x.x != y.x ? x.x < y.x : x.y < y.y;
		});
		a[0] = { 1, 1, 1 };
		a[s + k + 1] = { n, m, 1 };

		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		int last = 0;
		for (int i = 1; i <= s + k + 1; i ++) if (a[i].col) {
			for (int j = last + 1; j <= i; j ++)
				dp[j] = mul(dp[last], 
					ff(a[j].x - a[last].x, a[j].y - a[last].y, k1 + a[last].x - a[last].y, k2 + a[last].x - a[last].y));
			for (int j = last + 1; j <= i; j ++)
				for (int j1 = j + 1; j1 <= i; j1 ++)
					dp[j1] = sub(dp[j1], mul(dp[j], 
						ff(a[j1].x - a[j].x, a[j1].y - a[j].y, k1 + a[j].x - a[j].y, k2 + a[j].x - a[j].y)));
			last = i;
		}

		printf("Case #%d: ", ++ kas);
		printf("%d\n", dp[s + k + 1]);
	}
}

C++(clang++11) 解法, 执行用时: 1305ms, 内存消耗: 3640K, 提交时间: 2021-03-21 11:55:03

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F first
#define S second
using namespace std;
const int mm=1000000007;
typedef pair<int,int> P;

long long fac[2000009],invfac[200009];
void init(){
	fac[0]=invfac[0]=invfac[1]=1;
	for(int i=1;i<=200000;++i)fac[i]=fac[i-1]*i%mm;
	for(int i=2;i<=200000;++i)invfac[i]=invfac[mm%i]*(mm-mm/i)%mm;
	for(int i=1;i<=200000;++i)invfac[i]=invfac[i-1]*invfac[i]%mm;
}
long long C(int n,int m){
	if(n<0||m<0||n<m)return 0;
	return fac[n]*invfac[m]%mm*invfac[n-m]%mm;
}

int Tn;
int n,m,q1,q2;
vector<P>yes;
vector<P>no;

int check(P a){
	if(a.F>a.S)return 1;
	if(m+a.F<n+a.S)return 1;
	return 0;
}
P mirror(P a,int o){
	if(o==0){
		return P{a.S+1,a.F-1};
	}else{
		return P{a.S-m+n-1,a.F+m-n+1};
	}
}
long long go(P s,P t){
	return C(t.F-s.F+t.S-s.S,t.F-s.F);
}
long long calc(P s,P t){
	if(check(s)||check(t))return 0;
	long long ret=go(s,t);
	for(int o=0;o<=1;++o){
		int j=0;P a=s;
		for(;;){
			a=mirror(a,j^o);
			if(j==0)ret=(ret-go(a,t)+mm)%mm;
			else ret=(ret+go(a,t))%mm;
			if(go(a,t)==0)break;
			j^=1;
		}
	}
	return ret;
}
long long f[29];
long long work(P s,P t){
	if(check(s)||check(t))return 0;
	if(s.S>t.S)return 0;
	vector<P>q;
	q.push_back(s);
	for(int i=0;i<no.size();++i){
		if(no[i].F>=s.F&&no[i].F<=t.F&&no[i].S>=s.S&&no[i].S<=t.S){
			q.push_back(no[i]);
		}
	}
	q.push_back(t);
	f[0]=1;
	for(int i=1;i<q.size();++i){
		f[i]=calc(s,q[i]);
		for(int j=1;j<=i-1;++j){
			f[i]=(f[i]-f[j]*calc(q[j],q[i])%mm+mm)%mm;
		}
	}
	return f[(int)q.size()-1];
}

int main(){
	init();
	scanf("%d",&Tn);
	for(int tn=1;tn<=Tn;++tn){
		yes.clear();no.clear();
		scanf("%d%d%d%d",&n,&m,&q1,&q2);
		while(q1--){
			int x,y;scanf("%d%d",&x,&y);
			yes.push_back(P{x,y});
		}
		while(q2--){
			int x,y;scanf("%d%d",&x,&y);
			no.push_back(P{x,y});
		}
		if(n>m){
			printf("Case #%d: %lld\n",tn,0);
			continue;
		}
		yes.push_back(P{1,1});
		yes.push_back(P{n,m});
		sort(yes.begin(),yes.end());
		sort(no.begin(),no.end());
		long long ans=1;
		for(int i=1;i<yes.size();++i){
			ans=ans*work(yes[i-1],yes[i])%mm;
		}
		printf("Case #%d: %lld\n",tn,ans);
	}
	
	return 0;
}