[总结] 不是科技

双线翻转

前言

一次翻折可以帮助求出卡特兰数的一个公式：\(F(n)=\binom{2n}{n}-\binom{2n}{n-1}\)。

就是将卡特兰数与从 \((1,1)\) 走到 \((n,n)\) 且不碰到 \(y=x+1\) 的路径方案一一对应。

具体求法是容斥，首先总的方案是 \(\binom{2n}{n}\)，然后考虑减去碰到了 \(y=x+1\) 的方案；

考虑直接将终点按 \(y=x+1\) 对称，这样到新终点就必定会碰到这条直线，同时不难发现到新终点的每条路径都唯一对应原来一条非法路径。

拓展

如果即不能经过 \(y=x+1\) 还不能经过 \(y=x-m\) 怎么办呢？当然还是容斥。

总的方案依然是 \(\binom{2n}{n}\)，减去碰到 \(y=x+1\) 的方案就对 \(y=x+1\) 翻折再求组合数，减去碰到 \(y=x-m\) 的同理。

此时发现存在算重，于是想办法加上先碰到 \(y=x+1\)，再碰到 \(y=x-m\) 或者反过来的那些路径。

然后还要继续容斥……

最后结论就是，把终点交替按两条线翻折，对应的路径与原来按交替顺序碰到这两条线的路径一一对应。

int x = n, y = n, ans = C(x + y, y), p;
	auto rev1 = [&] (int &x, int &y) -> void{ swap(x, y), x -= 1, y += 1; };
	auto rev2 = [&] (int &x, int &y) -> void{ swap(x, y), x += m, y -= m; };
	p = 1, x = n, y = n;
	while(x >= 0 && y >= 0){
		if(p) rev1(x, y), MOD(ans -= C(x + y, y));
		else rev2(x, y), MOD(ans += C(x + y, y) - mod);
		p ^= 1;
	}
	p = 0, x = n, y = n;
	while(x >= 0 && y >= 0){
		if(p) rev1(x, y), MOD(ans += C(x + y, y) - mod);
		else rev2(x, y), MOD(ans -= C(x + y, y));
		p ^= 1;
	}
	cout << ans << endl;

\(O(\log)\) 查两个有序序列第 \(k\) 大

介绍

给你两个数组 \(a,b\)，长度分别为 \(n,m\)，现在要求第 \(k\) 大。

\(\log^2\) 的做法很常见，先二分第 \(k\) 大是多少，然后再二分有多少个数小于当前二分的值。

但是还有个 \(\log\) 做法是这样的：

int solve(int *a, int *b, int n, int m, int k){
	if(k == 1) return n && m ? min(a[1], b[1]) : n ? a[1] : b[1];
	int p = k >> 1; k -= p;
	int v1 = p <= n ? a[p] : inf;
	int v2 = p <= m ? b[p] : inf;
	if(v1 < v2) a += p, n -= p; else b += p, m -= p;
	return solve(a, b, n, m, k);
}

拓展

见 #52. 【UR #4】元旦激光炮

\(O(n)-O(1)\) 求 \(\le n\) 的两数的 \(\gcd\)

对于任意整数 \(n\)，可以表示为 \(abc=n\)，满足 \(a,b,c\) 要么 \(\le \sqrt n\) 要么是质数。

分解方式：分解质因数，放入当前 \(a,b,c\) 中最小的那个中。

那么计算 \(\gcd(x,y)\) 时，设 \(x=abc\)，显然可以分别计算 \(\gcd(a,y),\gcd(b,\dfrac{y}{(a,y)}),\gcd(c,\dfrac{y}{(ab,y)})\).

那么质数情况直接判断，否则调用预处理的 \(\le \sqrt{n}\) 的两两 \(\gcd\)。

高斯整数的 \(\gcd\)

高斯整数指的是形如 \(x+yi\) 的整数，其 \(\gcd\) 仍然可以使用辗转相除求得。

其意义在于，可以求出两个向量的 \(\gcd\)。

struct Cpx{
	LL x, y;
	Cpx operator +(Cpx t){ return {x + t.x, y + t.y}; }
	Cpx operator -(Cpx t){ return {x - t.x, y - t.y}; }
	Cpx operator *(Cpx t){ return {x * t.x - y * t.y, y * t.x + x * t.y}; }
	Cpx operator /(Cpx t){
		LD a = x, b = y, c = t.x, d = t.y;
		return {(LL)roundl((a * c + b * d) / (c * c + d * d)),
				(LL)roundl((b * c - a * d) / (c * c + d * d))};
	}
	Cpx operator %(Cpx t){ return *this - (*this / t) * t; }
	LL len(){ return x * x + y * y; }
};
inline Cpx gcd(Cpx x, Cpx y){ Cpx t; while(y.len()){ t = x, x = y, y = t % y; } return x; }