做题总结
sshwy
2020-04-20 14:21:41
## [子异和](https://www.luogu.com.cn/problem/P5127)
> 设 $f(S)=\bigoplus_{x\in S}x$，设$F(S)=\sum_{T\subseteq S} f(T)$。
>
> 给出一棵$n$个点带点权树。要求支持$m$次操作：
>
> - 路径的权值都异或$x$；
> - 求路径的权值集合的$F$值。
>
> $n,m\le 2\times 10^5,a_i\le 10^9$。
{% label @位运算 %} {% label @按位考虑 %} {% label @线段树 %} {% label @树链剖分 %}
首先考虑$F$怎么算。先按位考虑。那么问题转化为01集合的 $F$ 值。设该集合有$x$个$0$，$y$个$1$。那么可以得到$F(S)=2^{x+y-1}[y>0]$。于是我们发现这只和集合大小有关。
考虑树上的问题，那么我们的问题就转化为01点权树的操作。然而树链剖分维护的复杂度是$O(n\log_2^2n)$的，再加上按位考虑就是$O(n\log_2^3n)$的。
不妨把所有位合在一起考虑。因为我们只需要查询当前路径的第$k$位上是否有1。那么也就是查询路路径or。要支持路径or，路径xor，我们可以维护$a_u,b_u,c_u$分别表示当前区间的数哪些位都是1，哪些位都是0，哪些位是01都出现了的。那么在区间异或的时候对$a_u,b_u$做一些位运算即可。在向上合并信息的时候可以用$a,b$更新$c$。
总时间复杂度$O(n\log_2^2n)$。
[代码](https://www.luogu.com.cn/record/32966814)
## [Chiori and Doll Picking (hard version)](https://www.luogu.com.cn/blog/fuyuki/solution-cf1336e2)
> 给出一个非负整数集合$A$，设
> $$
> p_i=\sum_{S\subseteq A}\left[ \text{popcount}(\oplus_{x\in S}x)=i \right]
> $$
> 求$p_0,p_1,\cdots,p_m$。
>
> $n\le 2\times 10^5,m\le 53$。
{% label @线性基 %} {% label @meet in middle %} {% label @FWT %} {% label @组合数学 %}
先求出线性基$B$，设$B$能表出的数的集合为$S(B)$。那么答案显然就是线性基的数的答案乘$2^{n-|B|}$。
若$|B|\le 26$，则我们可以暴力枚举$S(B)$的数并统计答案。
若$|B|>26$，构造序列$A$，$A_i=[i\in S(B)]$。那么$A$有一些性质。不妨设$A$的FWT变换为$\hat{A}$。
性质1：$\hat{A}_i$的取值只能为$0$或$2^{|B|}$。
我们知道$\hat{A}_i=\sum_{j}A_j(-1)^{|i\and j|}$。而$A$中值为$1$的数只有$2^{|B|}$个，因此若$\hat{A}_i=2^{|B|}$，则必然满足：$\forall j\in S(B)$，$|i\and j|$是偶数。
那么这样的$i$一共有多少个？假设满足该条件的$i$的集合为$G$。那么容易发现，$\forall x,y\in G$，$x\oplus y\in G$，也就是说$G$有关于异或运算的封闭性。因此可以求出$G$的一个线性基$C$。容易发现$C$的大小是小于等于$m-|B|$的！因为你确定了$B$中自由元的值后，根据“偶数条件”，其他主元的值也确定了。
我们可以使用一些技巧做到$2^{m-|B|}$枚举$G$中的数。
那么我们再考虑FWT回去求答案，则
$$
\begin{align}
p_x
&=\sum_{i=0}^{2^m-1}[|i|=x]A_i\\
&=\sum_{i=0}^{2^m-1}[|i|=x]\frac{1}{2^m}\sum_{j\in G}\hat{A}_j(-1)^{|i\and j|}\\
&=\frac{1}{2^{m-|B|}}\sum_{j\in G}\sum_{i=0}^{2^m-1}[|i|=x](-1)^{|i\and j|}
\end{align}
$$
容易发现。后面的那个式子只和$|j|$有关，即$\sum_{i}[|i|=x](-1)^{|i\and j|}=g(x,|j|)$。那么我们想办法预处理$g(x,y)$即可。
$$
g(x,y)=\sum_{i=0}^{2^m-1}[|i|=x](-1)^{|i\and (2^y-1)|}=\sum_{z=0}^{\min(x,y)}\binom{y}{z}\binom{m-y}{x-z}(-1)^z
$$
不妨设$f(x)=\sum_{j\in G}[|j|=x]$，那么原式可以化为
$$
p_x=\frac{1}{2^{m-|B|}}\sum_{y=0}^{m}f(y)g(x,y)
$$
[代码](https://codeforces.ml/contest/1336/submission/77343381)
## [Exercise](https://loj.ac/problem/3284)
> 定义一个置换$P$的幂周期为最小$k$使得$P^k=I$。
>
> 求长度为$n$的所有置换的幂周期乘积$\bmod M$。
>
> $1\le n\le 7500$。
{% label @min-max 容斥 %} {% label @DP %} {% label @组合数学 %}
容易发现，幂周期是环长的LCM。由于求的是乘积，不妨对每个质因子$p$考虑指数的和。因此我们要求的就是所有幂周期中$p$的指数的和$\bmod (M-1)$。
设$E(p,x)$ 表示$p$在$x$中的指数。
假设环长是$l_1,l_2,\cdots,l_m$。那么$p$的指数就是$\max E(p,l_i)$。
$$
\begin{align}
\sum_{l}\max_{i=1}^m E(p,l_i)
&=\sum_{l}\sum_{\varnothing\subset S\subseteq [m]} (-1)^{|S|-1} \min_{i\in S}E(p,l_i)\\
&=\sum_{l}\sum_{\varnothing\subset S\subseteq [m]} (-1)^{|S|-1}\sum_{x\ge 1}\prod_{i\in S}[E(p,l_i)\ge x] \\
\end{align}
$$
不妨设
$$
f(x,p)=\sum_{l}\sum_{\varnothing\subset S\subseteq [m]} (-1)^{|S|-1}\prod_{i\in S}[E(p,l_i)\ge x]
$$
则原式化为$\sum_{x\ge 1}f(x,p)$。
考虑如何计算$f(x,p)$。容易发现，它相当于强制要求子集里的环长都是$p^x$的倍数。考虑DP。设$s=p^x$，设$g_i$表示$is$个数的贡献和。那么枚举第一个数所在环的长度，得到
$$
g_i=-\sum_{j= 1}^i(sj-1)!\binom{si-1}{sj-1}g_{i-j}
$$
前面的负号是容斥系数。那么$f(x,p)$就相当于$n$个数中选择$si$个数（剩下的$n-si$个数随便排），然后统计这$si$个数的贡献：
$$
f(x,p)=f'(s)=\sum_{i= 1}^{\lfloor\frac{n}{s}\rfloor} \binom{n}{si}(n-si)!g_i
$$
那么计算$f(x,p)$的复杂度就是$O(\frac{n^2}{s^2})$。则总复杂度就是$O(\sum_{i=1}^n\frac{n^2}{i^2})=O(\frac{n^2\pi^2}{6})$，能过。
注意，枚举的时候只枚举$p^x$，不要枚举非质因子幂的合数。
[代码](https://loj.ac/submission/792418)
## [删数](https://loj.ac/problem/3094)
> 对于任意一个数列，如果能在有限次进行下列删数操作后将其删为空数列，则称这个数列可以删空。一次删数操作定义如下：记当前数列长度为$k$，则删掉数列中所有等于$k$的数。
>
> 现在有一个长度为$n$的数列$a$，有$m$次修改操作：
>
> - 单点修改；
> - 所有数$\pm 1$。
>
> 求第$i$次修改后的$a$，至少需要修改几个数才能删空？
>
> $n,m\le 1.5\times 10^5,1\le a_i\le n$。
{% label @线段树 %} {% label @构造 %}
对于一个静态的序列如何求出答案？
考虑建立权值数组，$c_i$表示$i$的出现次数。那么不妨把$c_i$当成一摞方块，那么我们把这个柱子向左平推推倒，这样会覆盖$[i-c_i+1,i]$。对每个权值这样操作后，没有被覆盖的位置的个数就是答案。证明：从合法性和最优性两个角度。
那么对于修改操作，所有数$\pm 1$相当于是数组的平移，记个指针就行。单点修改也很好维护。
使用线段树维护。时间复杂度$O((n+m)\log_2n)$。
## [链上二次求和](https://loj.ac/problem/2512)
> 给出一个长度为$n$的整数序列$a$，有$m$次操作，要求支持区间加，询问
> $$
> f(l,r)=\sum_{i=1}^n\sum_{j=i}^n[l\le j-i+1\le r]\sum_{k=i}^j a_k \pmod{10^9+7}
> $$
> $n\le 2\times 10^5,m\le 5\times 10^5$。
{% label @线段树 %}
首先有一个小差分。
如果这个序列是一个环，那么答案就很好求。断成链之后，有些区间就不能统计到。对于长度为$x$的区间，那么$a_{n-x+1}$会少统计$1$次，$a_{n-x+1}$少统计$2$次……，$a_n$少统计$x-1$次。同理，$a_1$少统计$x-1$次，$a_2$少统计$x-2$次，以此类推。
那么对于长度小于等于$x$的区间，则系数就是$A=\{1,3,6,10，\cdots\}$，也就是$B=\{1,2,3,\cdots\}$的前缀和。只要能快速维护带系数的区间和即可。那么使用线段树维护，也就转化为，快速求出这两个序列的区间和。其中$1,2,3,\cdots$的很好求，而$1,3,6,\cdots$可以求出前缀和公式$S(i)=\frac{i(i+1)(i+2)}{6}$，当然也可以预处理。
然后还需要把$\sum_{L\le i\le R} A_ia_i$给转化为$\sum_{L\le i\le R}A_{i-L+}a_i$，那么这个可以用$\sum_{L\le i\le R}B_ia_i$和$\sum_{L\le i\le R}a_i$来辅助计算。处理一下细节即可。
时间复杂度$O(n\log_2n)$。
[代码](https://loj.ac/submission/792591)
## [Make Symmetrical](https://codeforces.ml/contest/1028/problem/F)
> 二维平面上，要求支持$q$次操作：
>
> - 插入一个整点$(x,y)$（$1\le x,y\le 10^5$），保证这个点之前没有插入过。
> - 删除一个点（之前插入过）。
> - 给出$(x,y)$（$1\le x,y\le 10^5$），求至少再加入多少个点可以使整个点集关于直线$((0,0),(x,y))$轴对称。
>
> $1\le q\le 2\times 10^5$。
{% label @暴力 %}
关于 $((0,0),(x,y))$ 轴对称的点，到原点的距离是相等的。而实际上满足$x^2+y^2=C$在固定$C$的情况下的点$(x,y)$的数量是不多的。在本题中至多有$144$个点。
不妨考虑，每次加入一个点的时候，我们$O(144)$地更新答案。然后查询的时候直接查表即可。
值得一提的是，在计算两个点的对称轴的时候由于这两个点到原点的距离相等，因此可以直接向量加法求出（菱形）。
用map维护。时间复杂度$O(q\log_2n\cdot 144))$，使用unordered_map可以更快。
[代码](https://codeforces.ml/contest/1028/submission/77597293)
## [Make Square](https://codeforces.ml/contest/1028/problem/H)
> 如果序列$b_1,\cdots,b_m$中存在两个数$b_i,b_j$（$i<j$）使得$b_ib_j$是完全平方数，则$b$是好的。
>
> 对于一个序列$b$，每次操作，你可以选择一个元素并乘上一个质数，或者选择一个元素并除掉一个质数。$f(b)$表示最少的操作次数使得$b$变成好的。
>
> 给你一个序列$a$，每次询问区间的$f(a[l,r])$。
>
> $n\le 2\times 10^5,q\le 10^6,a_i\le 5\times 10^6$。
{% label ＠DP %} {% label ＠二进制表示 %} {% label ＠异或 %} {% label ＠扫描 %}
首先想到把平凡因子去掉，这样每个数就最多有$7$个互不相同的质因子，即最多有$128$个约数。
现在，要让$ab$是完全平方数（即$a$到$b$的最短距离），则相当于$a$要先走到$a$的某个约数$x$，再从$x$走到$b$。
考虑扫描线DP。考虑$a_1,\cdots,a_i$，设$f(x,d)$表示最大的$j$（$j\le i$）使得$x\mid a_j$且$\frac{a_j}{x}$有$d$个质因子（即$x$走$d$步到$a_j$）。再设$g_x$表示最大（靠右）的$j$使得$[j,i]$的答案$\le x$。
考虑如何从$i-1$更新到$i$。加入一个$a_i$，则我们可以先枚举$x\mid a_i$，用$a_i$走到$x$再走$d$步来更新对应的$g$（即使$a_i$到$x$和$x$走的$d$步中有相同的质因数也没关系。因为我们求的是$\le$）。更新完$g$再用$x$走到$a_i$来更新$f$。
然后我们就可以求出以$i$为右端点的询问的答案了。
时间复杂度$O(n(\sqrt{a_i}+128\cdot 7)+q\cdot 14)$。
[代码](https://codeforces.ml/contest/1028/submission/77600817)