专栏文章

数学 Trick 之：双线 Catalan / 反射容斥

pporse
算法·理论参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mipy2gfw
此快照首次捕获于
2025/12/03 19:49
3 个月前
此快照最后确认于
2025/12/03 19:49
3 个月前
查看原文

能够解决的问题

形如这一类问题：从 (0,0)(0, 0) 到 (n,m)(n, m)，每次往上或右走，不能走到给定的两条直线。

优缺点

无

思路

首先，如果你不会单线做法，可以先看看 Catalan 的内容。
我们先回顾一下一条直线。
我们走了一个对称点来得到不合法的值，而且这里有一个重要性质：无论经过多少次直线，都可以通过走一个对称点来不重不漏地计数（下文称为 性质 11）。
我们考虑两条线的时候的不合法情况。
设两个直线为 l1,l2l_1, l_2。
根据 性质 11，连续经过一条直线可以算作一次，所以我们可以把不合法情况表达为 AA，BB，ABAABA，BABBAB，BABABBABAB，等（交替出现）。
此时我们考虑将目标点对 l1l_1 对称会怎么样。
此时有两种情况：
  1. 最后一个经过的是 l1l_1，如图。
此时后缀为 AA。
  1. 最后一个经过的是 l2l_2（图中显然不合法，只是演示用，但是这种情况确实会发生，不理解的可以画图）。
此时后缀为 ABAB。
综上，他统计后缀为 AA 或 ABAB 的方案数。但是他无法统计后缀为 BBBB 的方案数。想要得到后缀为 BBBB 的方案数，我们关于 l2l_2 对称即可但是我们会算重一些方案，比如 BABBAB（既有后缀 ABAB， 又有后缀 BB）。
那么，我们能不能求出只经过 AA 或 ABAB 的值方案数（请注意，这里说的不是后缀）？我们考虑把关于 l1l_1 对称的点再关于 l2l_2 对称（如图），此时又有两种情况：
  1. 最后一个经过的是 l1l_1，如图。
此时后缀为 BABA。
  1. 最后一个经过的是 l2l_2（图中不合法得更离谱了，只是演示用，而且这种情况也确实会发生，不理解的也可以画图）。
此时后缀为 BABBAB。
综上，他统计后缀为 BABA 或 BABBAB 的方案数，而且我们发现，将结尾为 AA 或 ABAB 的方案数减去结尾为 BABA 或 BABBAB 的方案数，就得到了只经过 AA 或 ABAB 的方案数！
同理，再关于 l1l_1 对称，得到后缀为 ABAABA 或 ABABABAB 的方案数，再关于 l2l_2 对称，得到后缀为 BABABABA 或 BABABBABAB 的方案数，相减，得到只经过 ABAABA 或 ABABABAB 的方案数，以此类推，直到当前点不在第一象限即可。
那么我们就解决了 AA，ABAB，ABAABA，ABABABAB，ABABAABABA，ABABABABABAB 等为后缀的方案数，此时还剩下 BB，BABA，BABBAB，BABABABA，BABABBABAB，BABABABABABA 等为后缀的方案数，而这些和前面几乎一模一样，只需要先关于 l2l_2 对称即可。
于是我们就解决了这类问题。

例题

Luogu P3266 [JLOI2015] 骗我呢
这道题的 dp 部分比较简单，观察到每行 mm 个数且值域为 0∼m0 \sim m，有 m+1m + 1 个数，所以定义 dpi,jdp_{i,j} 表示当前选到第 ii 行，这行不选 jj 的方案数，转移非常简单，直接写了： dpi,j=∑k=0j+1​dpi−1,kdp_{i,j}=\sum_{k=0}^{j+1​}dp_{i−1,k}，而且我们发现右边的东西就等于 dpi−1,j+1+dpi,j−1dp_{i−1,j+1}+dp_{i,j−1}，可以看作走路径（如图）：
我们把这张图斜着的边拉直（黑色部分），最左边的一列路径改成折线（红色部分），得到：
我们发现两条蓝线正好是 l1,l2l_1,l_2，题目转化成从 (0,0)(0,0) 到 (n+m+1,m)(n + m + 1,m)（不理解终点为什么在这的可以可以手搓一下），不碰到 l1,l2l_1,l_2 的方案数，用上文方法即可。

Code

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

#define int long long
constexpr int maxn = 3000010, modd = 1000000007;

int n, m, fac[maxn], invfac[maxn], ans;

int ksm(int a, int b) { // 快速幂
	int ress = 1;
	while (b) {
		if (b & 1) ress = ress * a % modd;
		a = a * a % modd;
		b >>= 1;
	}
	return ress;
}

void init() { // 阶乘初始化，用来加速组合数
	fac[0] = invfac[0] = 1;
	for (int i = 1; i < maxn; i++) {
		fac[i] = fac[i - 1] * i % modd;
		invfac[i] = ksm(fac[i], modd - 2);
	}
	return ;
}

int C(int a, int b) { // 组合数
	return fac[a] * invfac[b] % modd * invfac[a - b] % modd;
}

void mirrorL1(int &x, int &y) { // 关于 l1 对称
	int t = x;
	x = y - 1;
	y = t + 1;
	return ;
}
void mirrorL2(int &x, int &y) { // 关于 l2 对称
	int t = x;
	x = y + m + 2;
	y = t - m - 2;
	return ;
}

void solveA(int nowx, int nowy) { // A, AB, ABA, ABAB 情况的计数
	int flag = 0;
	mirrorL1(nowx, nowy);
	while (nowx >= 0 && nowy >= 0) {
		if (!flag) ans = (ans - C(nowx + nowy, min(nowx, nowy))) % modd;
		else ans = (ans + C(nowx + nowy, min(nowx, nowy))) % modd;
		flag ^= 1;
		if (flag) {
			mirrorL2(nowx, nowy);
		} else {
			mirrorL1(nowx, nowy);
		}
	}
	return ;
}
void solveB(int nowx, int nowy) { // B, BA, BAB, BABA 情况的计数
	int flag = 1;
	mirrorL2(nowx, nowy);
	while (nowx >= 0 && nowy >= 0) {
		if (flag) ans = (ans - C(nowx + nowy, min(nowx, nowy))) % modd;
		else ans = (ans + C(nowx + nowy, min(nowx, nowy))) % modd;
		flag ^= 1;
		if (flag) {
			mirrorL2(nowx, nowy);
		} else {
			mirrorL1(nowx, nowy);
		}
	}
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n >> m;
	
	init();
	ans = C(n + n + m + 1, n) % modd; // 总方案
	solveA(n + m + 1, n);
	solveB(n + m + 1, n);
	
	cout << (ans % modd + modd) % modd << '\n';
	
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...