MUH and Cube Walls CF471D
由于序列同时加 \(x\)，该序列的差分数组不变，所以求出 \(a,b\) 的差分数组跑 kmp 或哈希。
书柜
题目描述：
有 \(A,B\) 两种书排成的序列，序列长度为 \(n\)，两种书高度分别为 \(h_A,h_B\)，\(q\) 次询问每次给定一段区间，你需要移除一些书使得剩下的书严格递增，求剩下的书的最多数量。
\(n\le 5\times 10^6\)，\(q \le 5\times 10^5\)，空间限制 \(128\) MB。
发现若 \(h_A < h_B\)，询问区间内有子序列 \(AB\) 则答案为 \(2\) 否则为 \(1\)，反之亦然，所以若 \(a_i\) 为 \(A\) 则维护前面 \(B\) 出现位置的最大值记为 \(p0_i\)，\(a_i\) 为 \(B\) 同理，查询时求对应最大值是否大于区间左端点即可。
注意：最大值用树状数组维护，用线段树、ST表等数据结构会被卡空，树状数组建树要 \(O(n)\) 不然会被卡时，查询 \(O(\log^2 n)\) 就行。
Equation AT_arc158_d
对于任意三元组 \((x,y,z)\)，一定有一个数 \(t\) 满足：
\[(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n})\ \equiv\ t(x^{3n}+y^{3n}+z^{3n})\pmod{p} \]因为左式可以除右式，那么有：
\[(\frac{x}{t}+\frac{y}{t}+\frac{z}{t})((\frac{x}{t})^n+(\frac{y}{t})^n+(\frac{z}{t})^n)((\frac{x}{t})^{2n}+(\frac{y}{t})^{2n}+(\frac{z}{t})^{2n})\ \equiv\ t((\frac{x}{t})^{3n}+(\frac{y}{t})^{3n}+(\frac{z}{t})^{3n})\pmod{p} \]所以 \((\frac{x}{t},\frac{y}{t},\frac{z}{t})\) 就是一组合法的解，不断随机 \(x,y,z\)，如果 \(x \ne y \ne z\) 且左式右式的值均不为 \(0\) 就输出答案。
Teleporting Takahashi AT_abc240_g
先考虑一维情况，假设从 \(0\) 点走到 \(x\) 点，总共能走 \(n\) 步，\(a\) 步向前，\(b\) 步向后，很容易列出方程：
\[ \begin{cases} a+b=n\\a-b=x \end{cases} \]易得 \(a=\frac{n+x}{2},b=\frac{n-x}{2}\)，那么方案数就为为 \(C_n^a\)，注意若 \(n<x\) 或 \(\frac{n+x}{2}\mod2=1\)，则无解。
再考虑二维情况，将坐标系旋转 \(45^\circ\)，坐标 \((x,y)\) 就变成了 \((x+y,y-x)\)，此时移动增量变成了 \((+1,+1),(+1,-1),(-1,+1),(-1,-1)\) 两维互不干涉，那么问题就变为了两个一维的问题相乘即可。
扩展到三维，由于 \(-10^7 \le z \le 10^7\)， 枚举第三维往上走几步往下走几步，减去步数就变成了二维问题。
标签：10,le,frac,选讲,3n,序列,2n,杂题 From： https://www.cnblogs.com/Livedreamyhy/p/18186272