9.16~9.22 总结

做题

ARC156D

注意到 \(f(x^{2^k})=f(x)^{2^k}\pmod 2\)。然后问题是计算生成函数的乘积的答案。我的想法是考虑 \(f(x^{2^{10}})\) 的最低项大于 \(f(x)f(x^2)\dots f(x^{2^9})\) 的最高项，因此可以分位做。

但是若直接考虑拆位计算 \(i\) 位，这时考虑计算（和为 \(S\)） \(\lfloor \frac{S}{2^i}\rfloor\)。这样合法，因为前 \(i-1\) 位无关紧要。这个时候注意到因为在意最低位，\(i\) 以上 \(f(x^{2^j})\) 无贡献；所以得到值域应该是 \(O(n)\) 的。这时利用 bitset 做到 \(O(n^2\log k/\omega)\)。

P3251 注意到 bitmask 状态可以组织成树，因此考虑树上消元方法（表示为一次函数）计算。事实上具有相同 \(\min\) 和 \(\text{sum}\) 的可以统一计算，就可以 dp 了。

AGC038D 注意到 “有一条简单路径” 是传递的，因此先并查集合并。之后假如不考虑多条的最大边是缩点（点内部是树）后的完全图，最少是树。考虑多条的话需要连成环或者完全图。

又进行了和 hanghang 的 duel。

CF536D 不知道为什么有 *2900 的前缀和优化 dp。

CF1651E（duel） 注意到原图是很多环。然后子图就是偶环、偶链、奇链。最大匹配就是（点数-奇链）/2。统计每个奇链出现次数即可，这个可以暴力枚举。

CF1848E（duel）意思是 \((x+1)(2f-x)=2y\) 并且 \(\frac{y}{x+1}+\frac x2\ge x\)，即 \(x(x+1)\le 2y\)。此时还要求 \(2f-x\) 是整数，即 \((x+1)-1\) 和 \(\frac{2y}{x+1}\) 奇偶性相同，即 \(x+1\) 或 \(2f-x\) 为奇。注意到 \(x(x+1)\le 2y\) 意味着每一对积为 \(2y\) 的因数恰有一个满足条件。所以只需统计奇因数个数。使用线段树维护。

CF643E（duel）注意到输出小数，因此只需考虑 \(dep\le 50\)。然后直接 dp 即可。

CF1667C 神秘构造。首先注意到 \(k\le \lceil \frac{2n-1}{3}\rceil\)，而上界是可以取到的。考虑 \(n\equiv 1\pmod 3\)。这个时候在前 \(k\) 行列使用斜线覆盖，其余使用横竖覆盖。这个排列构造应该是容易的。其余情况类似。

CF1993F2 一次触碰到边界可以改成继续走，不修改，到原点的条件是 \(2w\mid x,2h\mid y\)。使用 excrt 合并同余方程。这个时候还需要转化 \(ax\equiv b\pmod m\)。方法是使用 exgcd 之后约 \(\gcd\)。

CF1398G（duel）FFT 处理 \(a_i-a_j\) 然后直接做。

CF963C（duel）这些矩形大小应该是 \(\{w_i\}\) 和 \(\{h_i\}\) 的笛卡尔积。这些个数因为形式是 \(a_i\times b_j\) 也应该成比例。因此不是无解就是 \(\omega(\gcd c_i)\)。

CF1957F2（duel）考虑把颜色给个哈希然后做个前缀和，然后到时候我只需要在上面二分就可以了。

CF1468L pollard-rho 分解然后巨大分讨。

CF1637H 一个重量级结论是每个逆序对选了前面一定选了后面。然后直接做就可以了。