24.10.14

A

只关心整数？

记 \(All\) 为全局和，\(sum\) 为矩阵和。

\(\dfrac{sum}{All - sum} = k\)，\(sum = \dfrac{k}{k + 1} All\)。

所以可能的矩阵和有约数个数个（一般取三次根号量级），然后枚举 \(x_1, x_2\)，从左往右扫 \(y\)，记录前缀和出现次数算答案。

B

啊？这么近的原？

24.10.10

A

数据范围弱化版：P2592。

\(n, m \le 10^7\)。

把一个看作 \(+1\) 另一个 \(-1\)，那么合法序列即为前缀和的最大值与最小值的差 \(\le k\)。在一维上不好写，上二维平面。

把向右走一步看作 \(-1\)，向上走一步看作 \(+1\)，那么每个格点代表的前缀和为 \(y - x\)，也就是要求路径上 \(\max(y - x) - \min(y - x) \le k\)。也就是划定两条直线 \(y = x + i,y = x + i + k\) 使路径不穿过这两条直线。

芝士反射容斥，可以看集训队论文再谈格路计数。也可以拜谢反射容斥 & exLucas 大蛇 NT。

令 \(n,m\) 是非负整数，\(l, r\) 是整数，满足 \(l < 0 < r, n + l < m < n + r\)，从 \((0, 0)\) 到 \((n, m)\)，始终不与 \(y = x + l\) 和 \(y = x + r\) 相交的格路数量为

\[|L((0, 0) \to (n, m) | x + l < y < x + r)| = \sum_{k \in \Z}\left(\binom{n + m}{n - k(r - l)} - \binom{n + m}{n - k(r - l) + r}\right) \]

使得组合数有意义的 \(k\) 是一个区间。只需要计算 \(O(\frac{n + m}{r - l})\) 个 \(O(n + m)\) 量级的组合数。

然后这个题里没有规定上下边界，只要求上下边界距离为 \(k\)，所以枚举上下边界，但是枚举之后发现每个上下边界距离为 \(\Delta\) 的路径被算了 \(k - \Delta + 1\) 次。那么记枚举上下边界距离为 \(k\) 算出的答案是 \(calc(k)\)，最终答案为 \(calc(k) - calc(k - 1)\)

这样复杂度是 \(O(\frac{n + m}{k} \times k ) = O(n + m)\) 的。

C

考虑每次修改点之后以修改点跑一次最短路。总之跑的飞快。

连边可以数论分块连，初始点权可以调和级数算。

D

【模板】2-SAT 计数

考虑把 2SAT 图建出来，缩点，此时缩完之后每一个点有一个与之对应的点，即为 \(inv_u\)，这两个点的取值必须不同。

传递闭包之后，如果有 \(u \to inv_u\)，或 \(inv_u\to u\)，那么这一对点的取值就确定了，高处的那个为 \(0\)，低处的那个为 \(1\)，就可以忽略这对点了。

然后考虑在经过上述处理的图中进行暴搜。若在限制的意义下不连通（即所有限制连边，\(u\) 与 \(inv_u\) 连边形成的图不连通），则答案显然是各个连通块的乘积。

否则，考虑选择某一个点 \(u\)，枚举它是 \(0\) 还是 \(1\)。若是 \(0\)，那么所有 \(i\to u\) 都是 \(0\)，所有 \(inv_u\to i\) 都是 \(1\)，若是 \(1\) 则反过来。

所以说，枚举了一个点的取值之后，会多确定能由它到达，或到达它的所有点。

我们试图选择这些点个数最大的那个，然后将其去掉递归。

题解复杂度分析：

去给初中学长写题解去了。

然后发现自己不会普及组串串题。