做题记录
CF2039F2
题目描述
对于一个包含 \(n\) 个元素的数据 \(a\)，定义 \(f(k)\) 表示数组 \(a\) 所有长度为 \(k\) 的子数组的最大值的最大公因数。
例如，对于数组 \([2,1,4,6,2]\)，\(f(3)=\gcd\{\max\{2,1,4\},\max\{1,4,6\},\max\{4,6,2\}\}=\gcd\{4,6,6\}=2\)。
定义一个数组 \(a\) 是好的，当且仅当 \(\forall 1\leqslant i<j\leqslant n\)，\(f(i)\neq f(j)\)。现在，给定一个数 \(m\)，请你算出任意非空的仅包含 \(1\) 到 \(m\) 内的所有整数的好的数组有多少个。由于这样的数组可能很多，答案请对 \(\textbf{998244353}\) 取模。
例如，当 \(m=1\) 时，所有满足上述要求的数组有 \([1],[1,2],[2],[2,1]\)，一共 \(4\) 个。
数据范围：
- \(t\) 组数据，\(1\leqslant t\leqslant 3\times 10^5\)。
- \(1\leqslant m\leqslant 10^6\)。
- \(\sum m\) 没有限制。
题解
场上差不多搞出了F1，不过没时间写了。
首先经过观察可以把这题转化为数值域为 \([1,m]\) 的单调降序列 \(\{a_i\}_{i=1}^n\) 使得 \(\forall i\in [1,n) \gcd_{j=1}^i a_j>\gcd_{j=1}^{i+1} a_j\)，且长度为 \(n\) 的序列贡献记为 \(2^{n-1}\)。
场上的思路是从大到小填数，记 \(f_{x,i}\) 表示当前末尾为 \(x\)，\(\gcd\) 为 \(i\) 的序列总贡献，转移即为 \(f_{x,i}=\sum_{y>x,j>i}2f_{y,j}[\gcd(j,x)=i]\)，这个东西显然是可以莫反优化的，那么F1就解决了。但是这个做法拓展性较差，最后我只会一个 \(\log^3\)。
然后是正解。其实我的状态可以进一步优化，考虑在从大到小枚举的时候记 \(f_i\) 表示当前状态下末尾 \(\gcd\) 为 \(i\) 的总贡献，加入一个数 \(x\) 的时候这个序列会改变
\[ \begin{aligned} f_i&\gets f_i+\sum_{k>i}2f_k[\gcd(k,x)=i] \\ &=f_i+2\sum_{d|x/i}\mu(d)\sum_{k}f_{idk}-2f_i \\ &=f_i+2\sum_{k|j|x}\mu(j/k)s_{j}-2f_i \\ \end{aligned} \]
观察这个转移，可以发现这个转移实际上是线性的，也就是说假如有状态
\[ [s_1,\cdots,s_n,f_1,\cdots,f_n,\Delta_1,\cdots,\Delta_n, 1]^T \]
这个转移可以看为一个矩阵 \(A_x\)，最后的答案就是
\[ [1,0,\cdots,0]\times A_1A_2\cdots A_m\times[0,\cdots,0,1]^T \]
那么可以对这个东西做一个转置，得到
\[ [0,\cdots,0,1]\times A_m^TA_{m-1}^T\cdots A_1^T\times[1,0,\cdots,0]^T \]
我们发现转置之后我们就可以从小到大枚举 \(x\) 了，添加一个 \(val\) 作为转置前状态中的 \(1\)，边枚举边记录答案就可以求出所有答案。转置操作体现在转移上就是把所有操作倒着做一遍，可能原本的影响是 \(sf\to \Delta\) 或 \(\Delta\to sf\)，那么转置后的影响变为 \(\Delta\to sf\) 或 \(sf\to \Delta\)，把每一步转移都当成乘上了一个转移矩阵，想一下这些小转移矩阵长啥样可能会比较好理解。
附上转置前后的代码：
1 | for (int i = n; i >= 1; i--) { |
1 | for (int i = 1; i <= 1000000; i++) { |
洛谷题解，感觉还是比较有启发意义？
Ucup 2nd Stage 21 Delft G
https://qoj.ac/contest/1511/problem/8213
显然a,aa,ab是平凡的，考虑长度为 \(3\) 怎么做，考虑dp，状态设计为 \(dp_{i,j,k}\) 表示 \(i\) 上的字母为 \(j\)，\(i\) 的父亲上的字母为 \(k\) 时子树 \(i\) 中最多能有几个贡献。那么在合并子树时只会增加以 \(i\) 为中心的串，分类讨论这部分贡献
aaa：周围有 \(k\) 个a时贡献为 \(k(k-1)\)aba：周围有 \(k\) 个a时贡献为 \(k(k-1)\)abb：周围有 \(k\) 个a时贡献为 \(k(deg_i-k)\)abc：这种情况的分析是本题的巧妙之处，结论是周围有 \(k\) 个a或c时贡献为 \(\lfloor\frac{k}{2}\rfloor\cdot\lceil\frac{k}{2}\rceil\)，这是因为我们可以翻转子树中的a和c，从而在不改变子树个数的情况下调整 \(i\) 周围a和c的个数，显然最大值就是该式。
所以我们只需要记录 \(dp_{i,0/1,0/1}\) 表示 \(i\) 点是否对 \(k\) 贡献了 \(1\)，\(i\) 的父亲是否对 \(k\) 贡献了 \(1\) 时子树 \(i\) 中最大贡献，且 \(4\) 种情况的转移是相同的，唯一的区别就是贡献的计算，这部分可以通过传入一个 lambda 函数处理，不需要写 \(4\) 个不同的dfs。
CF2046D
第一步显然缩点，得到无向图后考虑怎么做。
首先尝试判断可行性，可以用上下界网络流建模，把一个点 \(u\) 拆成两个点 \(u_{in},u_{out}\)，从 \(u_{in}\) 向 \(u_{out}\) 连边，容量下界为 \(1\)，\(S\) 向 \(u_{in}\) 连容量为 \(a_u\)，\(u_{out}\) 向 \(T\) 连容容量 \(\infty\) 的边，那么可行性等价于求解该有源汇上下界网络流是否有解。
最终建出来的图即为原题解中第二幅图。
考虑如何求答案，可以自然想到尝试给某些边加上cost转化为费用流问题求解。对每个点 \(u\) 添加 \(u_{cnt}\)，并连边：
- \(u_{cnt}\to u_{in}\)，容量为 \(\infty\)，费用为 \(1\)，这里容量可以为 \(1\)，因为每个点只会选择1个送信人，这样最优
- \(u_{cnt}\to u_{out}\)，容量为 \(\infty\)，费用为 \(0\)，这条边的流量保证 \(a_u\) 个送信人都可以出去
- \(S\to u_{cnt}\)，容量为 \(a_u\)，费用为 \(0\)，表示这个点的送信人数量
如果 \(u\) 有流入流量，那么就不用花费1代价走 \(u_{cnt}\to u_{in}\)，如果没有那么必须要花费1代价。
对这个图求最小费用最大流即可。
CF2034F2
F1的容斥非常简单傻逼无脑，但是我场上没想到。。。
F2的做法，先转成网格图边权1或2，然后有加倍点。考虑一条路径上的最后一条边，假设路径上特殊点的个数为 \(c\)，这条边的贡献是 \(w\cdot 2^c\)。
考虑将 \(2^c\) 拆贡献，注意到这是该边之前经过的关键点集合的子集数量。所以我们定义一个方案为一个条路径和其上的一个关键点集合，我们使一条路径上的某条边只在所有只选了该边之前的关键点的方案中被计边权的贡献即可，于是一个方案的权值就应为路径上方案内最后一个关键点到终点上所有边的边权和（若关键点集为空则为整个路径上的边权和）。
具体地，可以记 \(f_i\) 表示第 \(i\) 个关键点的系数，那么有
\[ f_i=\sum_{j}f_j\cdot \binom{x_i+y_i-x_j-y_j}{x_i-x_j} \\ ans=\sum_{i}f_i\cdot \binom{n+m-x_i-y_i}{n-x_i}\cdot(2(n-x)+(m-y)) \]
实际上这个做法好像能拓展到 \(t^c\)，把 \(t^c\) 拆成 \(\sum_{i=0}^{t-1}(t-1)t^{i}+1\)，反映到转移式上就是 \(f_i=\sum_j(t-1)f_j\cdots\)。