不在沉默中躺平，就在喧嚣中躺平。
但谁说人一定要躺平？我要 work work work work work work work work 勤劳又勇敢的 XSC062 为了 OI 的关键杂题集 她作出了巨大的贡献 巨大的牺牲 巨大的 carry 无敌了 无敌了 
[USACO23JAN] Moo Route G
https://www.luogu.com.cn/problem/P9018
关键词：由小推大 思维
希望大家不要和我一样忽略了重要条件：终点也是 \(0\)。这意味着每个点都会被左右成对地经过，那么不妨令 \(A_i\gets \frac 2{A_i}\)。
观察到给了 \(N=2\) 的一档分，考虑该情况。
若 \(A_1> A_2\)：
只要不拆开一组，箭头排列顺序任意。显然方案数为 \({A_1}\choose {A_2}\)。此时最优策略为……
|---------> <---------| |---------> <---------| |---------> <---------| |----> <----| |----> <----| =========== 0 1 2Otherwise：
此时最优策略为……
|----------> <----| |----> <----| |----> <---------| |---------> <---------| =========== 0 1 2相似地，只要不拆开一组，箭头排列顺序任意，可以注意到除了第一个，每个长
|--->的前面一定是一个长<---|，那么问题转化为选择 \(A_1-1\) 个短<---|拉长，方案数为 \({A_2-1}\choose{A_1-1}\)。
进一步，考虑 \(N=3\) 的情况。若已知子问题 \(0\to1\to2\) 的方案和子问题 \(1\to2\to3\) 的方案，可以直接乘起来合并。为什么呢？
二者经过 \(2\) 的次数相等；在子问题 \(0\to1\to2\) 中，\(1\to2\) 的下一步一定是 \(2\to 1\)；我们把该过程替换为子问题 \(1\to 2\to 3\) 中对应的一段 \(1\to2\to\cdots\to2\to1\) 的路径即可。
那么两两合并起来，可以得到最终答案为 \(\prod\limits_{i=1}^{n-1}\begin{cases}{\binom{A_i}{A_{i+1}}}&A_i>A_{i+1}\\{\binom{A_{i+1}-1}{A_i-1}}&\text{otherwise}\end{cases}\)。
#include <bits/stdc++.h>
const int lim = 5e5;
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], a[i] /= 2;
std::vector<long long> inv(lim + 1), fac(lim + 1);
auto qkp = [&](long long x, int y) {
long long res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[0] = fac[0] = 1ll;
for (int i = 1; i <= lim; ++i)
fac[i] = fac[i - 1] * i % mod;
inv[lim] = qkp(fac[lim], mod - 2);
for (int i = lim - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
long long res = 1ll;
for (int i = 1; i < n; ++i)
if (a[i] > a[i + 1])
(res *= C(a[i], a[i + 1])) %= mod;
else
(res *= C(a[i + 1] - 1, a[i] - 1)) %= mod;
std::cout << res << '\n';
return 0;
}[GDKOI2024 普及组] 正方形扩展
https://www.luogu.com.cn/problem/P10078
关键词：分类讨论 扫描线
理论上看懂了就是弱智题，可惜看不懂。
就是说，一个点如果被染了某种颜色，并且以它为中心的边长为 \(2\) 的正方形中没有其他颜色的点，就把这个正方形里的点都染成这个颜色，问每个颜色面积是否能达到无穷大。
考虑无法达到无穷大的原因，一定是因为向四个方向都无法延伸到无穷远。以右边为例，考虑点 \(i\) 什么时候不能在 \(x\) 轴正方向上延伸到无穷远：
对于 \(\forall \, j,x_j\le x_i\)，\(j\) 不会对 \(i\) 向右的延伸带来任何影响——所有点的延伸速度相同。
对于 \(x_j>x_i\) 且 \(y_j=y_i\)，\(j\) 可以堵住 \(i\)。
这时候不免产生疑问：\(i\) 不能从上下「翻越」过 \(j\) 的统治吗？
显而易见地，由于延伸速度相同，\(i\) 在某时刻能够在 \(y\) 轴上到达的高度，\(j\) 也能达到，所以 \(j\) 能够把 \(i\) 堵死，参见题面中给出的例子。
对于 \(x_j>x_i\) 且 \(y_j \ne y_i\)，由上所述，\(j\) 在 \(y\) 轴下 / 上方向无法追上 \(i\)，\(i\) 可以从该方向越过 \(j\)，在 \(x\) 轴正方向上延伸到无穷远；但 \(j\) 在自己所在的一侧（上 / 下）可以堵住 \(i\)。
对于 \(x_j,x_k>x_i\) 且 \((y_j-y_i)(y_k-y_i)<0\)（即二者分居 \(i\) 点上下），\(j\) 和 \(k\) 可以在两个方向分别拦截住 \(i\)。
此时可能有疑问：\(i\) 可不可以先越过 \(j\) ，再越过 \(k\) 呢？答案是否定的。由上，\(j\) 和 \(k\) 会分别在 \(y\) 轴自身对应方向上堵住 \(i\)，在越过其中之一后无法从这一侧越过另一个点，所以 \(i\) 会被两个点合作堵死。
由此我们总结出，\(i\) 能在 \(x\) 轴正方向被拦截，当且仅当：
- 存在 \(x_j>x_i\) 且 \(y_j=y_i\)；
- 抑或，存在 \(x_j,x_k>x_i\) 且 \(y_j<y_i,y_k>y_i\)。
那么可以从四个方向分别用扫描线求解。鉴于和实际坐标数值没有什么直接关系，可以离散化后树状数组以避免被卡常。