A
如果 \(i\) 可以继续往前走，那么必然存在 \(j \ge i > a_j\)，对于每个 \(i\) ，将 \((a_i, i]\) 加一，从 \(x\) 能走到的最小点就是 \(x\) 左侧第一个 \(0\)。线段树区间加，线段树二分。
B
要求一条边强制经过，就确定了所有棋子的路径，两条边能同时选当且仅当它们确定的路径一致。用随机异或哈希判断两条边确定的路径集合是否一致。线段树维护区间异或。
C
#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (long long i = (a), i##end = (b); i >= i##end; --i)
using namespace std;
using LL = long long;
const int N = 8010;
const LL mod = 1e9 + 7;
/**
* 钦定子序列在最左的出现位置统计
*
* 设 f[i] 表示考虑到 i 且钦定 i 在 T 内的答案, 枚举上一个钦定点 j,
* 考虑将 (j, i) 中的数填入 S 的方案数, 限制
* - ∀p∈(j, i) a[p] = a[i], a[p] 不能选 (不然不是 T 中最左)
* - 令 l 为最大的 p∈(j, i) 使得 a[p] = a[i], 必须 ∃q∈(l, i) a[q] 选入 S (不然该方案应在 l 处被统计)
* - 对 S 中每相邻两个数 p, q, 要求 ∀k∈(p, q), a[k] != a[q] (不然不是 S 中最左) // 同单子序列 dp 限制
*/
int n, a[N];
LL f[N], g[N];
int main() {
cin >> n;
rep(i, 1, n) cin >> a[i];
f[0] = 1;
rep(i, 1, n + 1) {
f[i] = f[i - 1];
// 从后往前跑本质不同子序列个数放到 S, 要满足上述条件
LL sum = 0, flag = 1;
memset(g, 0, sizeof g);
per(j, i - 1, 1) {
if (a[j] == a[i]) flag = 0;
else {
LL tmp = sum;
sum = (sum - g[a[j]] + mod) % mod;
g[a[j]] = tmp + flag;
sum = (sum + g[a[j]]) % mod;
}
f[i] = (f[i] + f[j - 1] * (sum + flag) % mod) % mod;
}
}
LL sum = 0;
memset(g, 0, sizeof g);
rep(i, 1, n) {
LL tmp = sum;
sum = (sum - g[a[i]] + mod) % mod;
g[a[i]] = tmp + 1;
sum = (sum + g[a[i]]) % mod;
}
// 把没选 T 的方案减去
cout << (f[n + 1] - sum - 1 + mod) % mod << endl;
return 0;
}
AT_arc184_b
是我没见过的轮廓线。
把没有因数 \(2, 3\) 的数 \(u\) 拿出来，生成一个这样的矩阵：
\[\begin{matrix} 2^03^0u & 2^03^1u &\cdots & 2^03^qu & \cdots \\ 2^13^0u & 2^13^1u &\cdots & 2^13^qu & \cdots \\ \vdots & \vdots & \ddots & \vdots & \ddots \\ 2^p3^0u & 2^p3^1u &\cdots & 2^p3^1u & \cdots \\ \vdots & \vdots & \ddots & \vdots & \ddots \end{matrix} \]只保留其中 \(\le n\) 的元素。易得每个 \(u\) 生成的所有元素集合不交。
对于一个矩阵，一次操作可以把选择的数以及它右边，它下边的数覆盖，要求用最少操作数覆盖所有 \(\le n\) 的元素。
轮廓线 dp，设 \(f_{i, j, sta}\) 表示考虑到 \((i, j)\)，轮廓线被覆盖情况是 \(sta\) 的最少操作次数。按照普遍轮廓线写法，前两维滚掉。
偷一下尺子姐姐的图
这个轮廓线不一样的地方在哪里咧，常见至少我见过的轮廓线压的都是已处理部分，这里压的是待处理部分。确切点是被已处理部分更新过的待处理部分。
转移时如果当前位已被覆盖，那么可选可不选，注意如果不选那么下一行同列没有被覆盖，对应的下一状态第 \(j\) 位应是 \(0\)；如果选的话更新第 \(j\) 位和第 \(j + 1\) 位都是 \(1\)。如果没被覆盖就必须选。
然后对于没有 \(2, 3\) 因数的数，如果矩阵形状相同，那么答案相同。然后至少 \(\left\lfloor\dfrac{n}{u}\right\rfloor\) 相同的 \(u\) 矩阵一定一样，可以数论分块求解。
P2081
（基环）树形 dp。
令 \(scnt_x\) 表示 \(x\) 子节点个数，\(fcnt_x (\in \{1, 2\})\) 表示 \(x\) 父节点个数。
\(Down_x\) 表示从 \(x\) 出发，第一步向子节点走的期望长度。\(Up_x\) 表示第一步向父节点走的期望。
\[Down_x = \frac{\sum_{y \in son_x}(Down_y + w(x, y))}{scnt_x} \]如果 \(x\) 不在环上
\[Up_x = w(x, fa_x) + \frac{Up_{fa_x} \cdot fcnt_{fa_x} + Down_{fa_x}\cdot scnt_{fa_x} - Down_{x} - w(x, fa_x)}{fcnt_{fa_x} + scnt_{fa_x}-1} \]第一步的贡献是 \(w(x, fa_x)\)，然后可以向上走或是换个儿子向下走，需要排除 \(x\) 的贡献。
特别的，如果 \(fa_x\) 只与 \(x\) 连边（\(fcnt_{fa_x} + scnt_{fa_x} - 1 = 0\)），那么 \(Up_x = w(x, fa_x)\)。
如果 \(x\) 在环上
先得到 \(dfn_x\) 表示环上第几个点，\(dcnt\) 环上点个数，\(rnk_i\)：\(dfn\) 反数组，\(disl_x, disr_x\)：\(x\) 向左，右的边长。
\[Up_x = \sum_{i \operatorname{from} dfn_{x} + 1 \operatorname{to} dfn_{x} - 1}P_i \times\left(\frac{Down_{rnk_i}scnt_{rnk_i}}{scnt_{rnk_i} + 1} + disl_{rnk_i}\right) + \sum_{i \operatorname{from} dfn_{x} - 1 \operatorname{to} dfn_{x} + 1}P_i' \times\left(\frac{Down_{rnk_i}scnt_{rnk_i}}{scnt_{rnk_i} + 1} + disr_{rnk_i}\right) \] 标签：rnk,Down,18,sum,24.10,scnt,fa,mod From： https://www.cnblogs.com/KinNa-Sky/p/18491543