2022/04/04 做题记录

AT4352

考虑容斥，答案就是 $\sum_{S \in E} (-1)^{|S|}f(S)$

其中 $f(S)$，是对于断开 S 后的所有联通块内随便配对的方案数。

考虑带着容斥系数 dp，设 dp[i][j] 表示在 i 这个节点，目前与 i 联通的未闭合联通块大小为 j 的方案数（不考虑联通块内的方案），而我们在 dp[i][0] 处处理联通块内的方案，显然 dp[i][0] 就是从其它的 dp[i][j] 中把大小为 j 的那个联通块闭合，这个方案数大概就是个双阶乘，而且因为联通块闭合那么钦定的 S 就多了一条从 i 到父亲的边，将方案数乘个 -1 即可，其它的转移就是树上背包。

最后答案就是 -dp[1][0] （因为最后多乘了个 -1）

code: /code/2022.4.4/AT4352.cpp

bzoj2082

直接 Pollard-Rho，之后答案显然。

code: /code/2022.4.4/bz2082.cpp

bzoj3674

可持久化线段树维护 fa 数组。

code: /code/2022.4.4/bz3674.cpp

CF464C

可以建一个 n+2 层的分层图，每层 10 个点代表这一时刻的 0～9，其中第一层用 0 依次向 s 的每一位连边，最后一层就代表 0~9，其它的向这次操作后它会变成的数每一位依次连边（如果删除就不连任何边），可以从后往前 dp ，记录这个数最后变成的位数和取模后的值，用费马小定理合并即可。

code: /code/2022.4.4/CF464C.cpp

CF932F

可以直接李超树维护跳到子树内所有点的费用，而李超树合并的时候就将对应节点一个中的直线插入到另一个，因为动态开点李超树中一条直线只会出现一次，而插入操作至少会让一条直线在树上的深度 +1 或者消失，于是复杂度是一个 log 的。

https://www.luogu.com.cn/blog/_post/182726

code: /code/2022.4.4/CF932F.cpp