\(\mathcal {I~Hate~NTT~}\)
边界开闭找清楚
指针空悬判清楚
时空复杂算清楚
特殊情况模清楚
math.h 加清楚
思路正确证清楚
using uint = unsigned int，在代码中非负的地方都用 uint，需要注意溢出的可能，尤其是两者相减的时候。
利用 fread 优化读入，主要是代码有点长。
取模的时候有 x >= mod && (x -= mod); 优化掉 if。
优化算法其实就是对于信息的充分利用，将信息的价值最大化。
无论是性质还是什么的，都属于信息的部分。
这是最核心的方法，是开始，也是终止。
记忆化搜索是最简单的，但是也是最直观的符合优化算法的本质的方法。
核心在于利用变量中的不变量，以此求出不同状态下的答案。
重点就转化为状态的定义，状态不应该和方案相关，它可以是一个性质，一个区间，一个点，甚至一个边。而状态也不应该被后面的状态限制。
这是个小技巧，已经用这个方法切了两道 \(T1\) 了 QwQ。
其用的前提在于对于一条边，经过前无论状态如何都不会影响后面的答案。
其复杂度为 \(O(m)\)，但是需要带上 \(6\) 倍的常数，不过可以接受。
属于是特类的记忆化了。通过增量维护某个信息，然后基于前面某个状态的信息求解。
DDP 就属于动态的动态规划，本质在于维护增量的叠加，然后统一转移。
目前有三种套路：
换根 DP
基于边的记忆化
找到点对于其他点的贡献
如何理解依据边的记忆化搜索：可以理解为对于一个点，不同的根会造成不同的父亲，于是记忆化每一个点给不同父亲的贡献即可。
一般来说，还是有套路的：
组合计数，利用组合数直接求解。
转换计数，也就是转换模型，再利用组合计数。而转换也有一定的套路：
flip，\(..08.26\) explorer，\(..08.28\) ring加法原理，分情况讨论。
容斥原理，总方案数好算，但是目标方案数不好算，就可以考虑这么算。有 \(2023.08.28\) ring，mex（题解做法），\(..08.30\) au
乘法原理，将答案分成两个部分，并且每个答案两个部分间有共用的部分。有 \(2023.08.28\) mex
参考例题：[yLOI2019] 梅深不见冬 - 洛谷，皇后游戏 - 洛谷，[NOIP2012 提高组] 国王游戏 - 洛谷。其中皇后游戏极其经典。
考虑证明该如何证明，据此看来有两种证明方法：
假定上一个状态固定，考虑这一次先放 \(i\) 再放 \(j\) 或者反过来的贡献。可能会存在类似于 \(\max(last, a) \le \max(last, b)\) 的存在，可以通过分讨，与题意产生神秘的冲突然后消掉。于是可以得到 \(a \le b\) 的某种偏序关系。
也可以考虑从 \(0\) 开始，也就是没有初始的情况，得到一个结论，然后归纳证明。
这种题该是有比较明显的特征，也就是最小化最后一个值，并且是需要枚举一个排列（代表着朴素的做法为 \(O(n!)\)。所以我们把它变成一种偏序，并以此作为排列依据求出最合理的排列即可。
设
考虑莫队转移：
而还有一种 \(O(n \sqrt n)\) 预处理，\(O(\sqrt n)\) 询问的方法（其实还可以减少其常数以提升其上界），如图：
每隔 \(\sqrt n\) 设置一个断点，在杨辉三角上向上跳即可。
预处理空间是 \(O(n \sqrt n)\) 的，但是可以通过离线变为 \(O(\sqrt n)\)，如果在每一层微调，那么可以做到 \(\sum_{i = 1}^n \sqrt i\)，虽然还是 \(O(n \sqrt n)\)，但是小常数。
考虑求 \([x \equiv y \pmod p]\)，有 \(p | x - y\)。
于是
P5591
利用有封闭形式的式子和单位根反演可以批量生产好题。
对于求形如：
有一些些套路。
类似扫描线的思路，\(O(n)\) 扫描右端点，考虑利用数据结构或者性质维护，更新后缀和。
分治，考虑分治经过 \(mid\) 的线段的贡献，只要可以对于每一个左端点 \(O(1)\) 或者 \(O(\log n)\) 求，就可以做到 \(O(n \log n)\) 或者 \(O(n \log^2 n)\)。
不过需要注意边界的问题，对于 \(mid\)，两个端点的区间为 \([l, mid], (mid, r]\)，或者采用左闭右开区间 \([l, mid), [mid, r)\)。
对于求形如：
类似的也有一些些套路：
\(O(n^2)\) 枚举上下端点，考虑 \(O(n)\) 求解，总复杂度为 \(O(n^2 m)\)。
\(O(\log(nm))\) 分治矩形，考虑 \(O(nm)\) 合并，总复杂度为 \(O(nm \log (nm))\)。类似于一维分治，需要注意区间边界问题：\([l, mid], (mid, r]\)。
考虑 \(O(n \log n)\) 基于上一行求此行，总复杂度为 \(O(nm\log n)\)。
如果满足区间加的信息，可以考虑 \(nm\log n \log m\) 预处理分解矩阵，每次矩阵求和（合并）做到 \(q \log n \log m\)。有点类似于 Spare Table 的小常数区间和的求法。
这是对于上面两个分点的一个小小的汇总。
都可以利用类似分治的思路。将求答案的部分小小合并一下。
如何分？考虑一般的套路：
\([l, mid]\) 和 \((mid, r]\) 的分治。
枚举长度 \(len\)，考虑 \((i - len, i], [i, i + len)\) 的贡献。也就是撒点，然后求，也就是 NOI 优秀的拆分的正解做法。
扫描线的思路
考虑优化 \(O(n)\) 求解的复杂度
本质上是考虑数据分治后产生单面贡献的情况。
例如多维偏序，半在线卷积等都可以利用 CDQ 分治。
也就说如果空间没有开够，那么溢出的贡献不会消失，而是转移到最前面。
减法卷积 优化时空常数。
对于：
翻转 \(f\) 有：
发现，\(h_i\) 实际上是得出卷积的第 \(i + n\) 项。
如果取长度 \(2n\)，溢出的部分贡献到 \([0, n)\)，不会对 \([n, 2n)\) 造成影响，所以可以放心大胆的溢出。
常数优化 \(\frac 23\)。
主打一个短代码，小常数。
但是最难的是整理出根号式子。
遇到 \(n^k\) 考虑转化为斯特林数：
然后进行种种神秘的操作变化式子。
对于 \(n\) 阶多项式 \(f\) 已知 \(f(0), f(1), \cdots, f(n)\)。需要求：
存在结论，存在一个 \(n\) 阶多项式 \(g\) 满足：
可以参见 whx 的 blog。
所以可以考虑 \(O(n)\) 差值求出 \(g(k + 1)\) 即可求出 \(S(k)\)。
对于 \(n + 1\) 个点 \((x_i, y_i)\)，考虑拉格朗日差值公式：
最终的式子是：
考虑如何快速求出 \(f_i(x)\)。
首先是分子部分，可以考虑利用前后缀和。
其次是分母，假定 \(x_0\) 最小，\(x_n\) 最大，所以对于 \(x_i\) 的分母部分为：
\(O(n)\) 预处理阶乘即可 \(O(1)\) 算出。
于是剩下的问题就是如何对于所有的分母求逆。
类比阶乘求逆元的方法，先求出前缀积，求逆后逆推出前缀积的逆。利用这两者即可求出每一项的逆。复杂度为 \(O(n + n + \log n) = O(n)\)。
于是 \(O(n)\) 算出最终答案即可，总复杂度为 \(O(n)\)。常数还行，大概为 \(8\)，因人而异。
// 来自 https://www.luogu.com.cn/problem/AT_arc033_4
// x_0 = 0, x_n = n
// 循环较多是考虑到缓存友好问题
lint qpow(lint a, int x) {
lint r = 1;
for (; x; x >>= 1, a = a * a % mod)
if (x & 1) r = r * a % mod;
return r;
}
int n, x;
lint y[N];
lint pre[N], suf[N];
lint fac[N], rfac[N];
lint up[N], down[N];
lint tmp[N], dinv[N];
int main() {
scanf("%d", &n); ++n;
for (int i = 1; i <= n; ++i)
scanf("%lld", y + i);
scanf("%d", &x);
pre[0] = suf[n + 1] = 1;
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] * (x - i + 1) % mod;
for (int i = n; i; --i)
suf[i] = suf[i + 1] * (x - i + 1) % mod;
fac[0] = rfac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
for (int i = 1; i <= n; ++i)
rfac[i] = rfac[i - 1] * (mod - i) % mod;
for (int i = 1; i <= n; ++i)
up[i] = pre[i - 1] * suf[i + 1] % mod;
for (int i = tmp[0] = 1; i <= n; ++i) {
down[i] = fac[i - 1] * rfac[n - i] % mod;
tmp[i] = tmp[i - 1] * down[i] % mod;
} tmp[n] = qpow(tmp[n], mod - 2);
for (int i = n; i; --i) {
dinv[i] = tmp[i] * tmp[i - 1] % mod;
tmp[i - 1] = tmp[i] * down[i] % mod;
}
lint ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + y[i] * up[i] % mod * dinv[i] % mod) % mod;
} printf("%lld\n", ans);
return 0;
}
牛顿级数形如：
考虑差分在 \(0\) 处的取值：
由于仅 \({0 \choose 0} = 1\) 所以 \(= c_n\)。
问题转化为求 \(\Delta^k f(0)\)，根据差分序列性质：
这是一个卷积形式，所以可以 \(O(n \log n)\) 求出所有的 \(c_i\)。
反之，类似二项式反演的式子，也可以 \(O(n \log n)\) 求出 \(0 \sim n\) 的点值。
存在欧拉回路的条件：对于有向图，每个点出度等于入度。
由于存在双向边，所以考虑 \(d_x = in_x - out_x\)，如果 \(d_x \& 1\) 那么一定无解。
欧拉回路实质是出度和入度的转移，故利用网络流求解。
注意对于一个不存在负环的图，从起点到任意一个点最短距离经过的点最多只有 \(n\) 个。
也就是说，一个点的松弛路径最多为 \(n\) 。
所以在 SPFA 中可以如此写：
if (dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
if ((cnt[y] = cnt[x] + 1) > )
}
复杂度还是 \(O(nm)\)，但是平均表现好很多。
但是还是不够快，考虑基于 DFS 的 SPFA 判负环，这是相对最快的。
注意初始化时 \(dis_x = 0\)，以及每一个点都需要 DFS 一次！
bool SPFA(int x) {
vis[x] = true;
for (auto e : G[x]) {
if (dis[e.to] > dis[x] + e.w) {
dis[e.to] = dis[x] + e.w;
if (vis[e.to]) {
vis[e.to] = false; return true;
} else if (SPFA(e.to, mid)) {
vis[e.to] = false; return true;
}
}
}
return vis[x] = false;
}
bool check() {
fill(dis + 1, dis + 1 + n, 0);
for (int i = 1; i <= n; ++i)
if (SPFA(i)) return true;
return false;
}
好东西，可以做到 \(O(\log^2 n)\) 单点修改（基于 vector erase 和 insert 的复杂度，这里视作 \(O(\log n)\)，还是蛮快的），\(O(\log^2 n)\) 求 \(rank(x)\)，\(O(\log^2 n)\) 求前驱或者后继，只是需要 \(O(\log^3n)\) 找到 \(kth(k)\)。
这不比树套树香多了？可是不如分块，\(\log^2 n\) 和 \(\sqrt n\) 在 \(1e5\) 差不了太多，分块对于缓存还更友好一些。
关系，例如食物链的关系，同类，猎物。
认为有三种角色，自己，猎物，天敌，分别维护 是 的关系即可。
扩展出来，发现对于关系，找出链循环长度，维护长度个并查集即可。
有没有一种可能，倍增建图并不需要划分为 \(O(\log n)\) 个区间，而是类似于 Spare Table 的做法，两个区间即可。（当然，前提是可以如此。
Buy Low Sell High - 洛谷 也就是维护反悔答案的插值，从而得到全局最优解。
好吧，本质上就是反悔贪心，只是利用 \(\Delta\) 优化了而已 QwQ