2022/04/10 做题记录

【BJOI2014】欧拉

设 $x=\prod p_i^{k_i}$，则 $\phi(x)=\prod p_i^{k_i-1}(p_i-1)$,前边一部分指数可能为0，所以枚举 $y$ 的因数找出所有可能的 $p_i-1$，然后把所有 $p_i$ 从大到小排序（为了尽快找到交优解）后 dfs 即可。

code: /code/2022.4.10/ac8149.cpp

Flow

考虑网络流最小割建模，把每个点拆成两个，原点向第一排中权值为正的点连 $v_i$ 的边（割掉代表不选），第一排中权值为负的点向汇点连 $-v_i$ 的边（割掉代表不选），第一排的点向对应的第二排的点连 $p_i$ 的边（割掉代表连续 k 级的祖先中存在没选的），第二排的点向这个点在树上连续 k 级祖先对应的第一排的点连权值为 inf 的边。

一个正权点选了会导致原点和它对应的第二排点联通，一个负权点被选了的实际意义是它与汇点连的边被割了，而这条边能被割说明源点一定与这个点对应的第一排点联通，那么就也与这个点对应的第二排点联通，接下来只需要考虑是否连续 k 级祖先中任意一个点没选都会导致第二排点与汇点联通（也就会导致一、二排点中间的边被割），如果有一个负权祖先没被选显然会导致，而一个正权祖先没被选的实际影响是原点与这个正权祖先的第一排点中间的边被割，而它被割一定是因为这个点与汇点联通（否则没有割的必要），于是得证。

第二排点向第一排点连的边需要树链剖分+线段树优化建图，因为边权都是 inf 线段树内也都连 inf 就行。

code: /code/2022.4.10/ac10464.cpp

CF341D

发现我们可以维护以每个点为右下角的 $2*2$ 矩形的异或和，这样修改的时候只有四个点的权值会变（因为其它点都被异或了两次），而询问的时候我们可以转化成二维前缀异或和，但是这个异或和坐标每次是 -2 的，于是我们可以按照 x,y 的奇偶性分到四个树状数组里去，这样每次询问在一个树状数组中就是连续的了。

code: /code/2022.4.10/CF341D.cpp

P2144

设 F_i 为考虑了前 i 个基原子的方案数

$$F_0=1, F_i =\sum_{j=0}^{i-1}F_j(i-j)$$

发现这样会导致无法考虑 (1,n) 这条边被覆盖的情况，于是可以设一个 $G_i = \sum_{j=2}^{n} (j-2+1)*j*F_{i-j}$,于是 $F_n +G_n$ 就是答案，手算一下 F 和 G 的高维查分，发现算到 2～3 维的时候形式就足够简单了（前缀和），于是写个高精度然后递推就行。

code: /code/2022.4.10/P2144.py