CF Edu123 题解

F. Basis

题面

考虑一群在操作 2 下可以互相变换的数组, 在其中可以取一个代表元$arr$。假设$arr$$i$种数字组成, 把$arr$中数字$j$所在的下标的集合记作$S_j$, 则这一群数组可以用集合的集合$\{S_1,S_2,...,S_i\}$来表示, 称为一个原型。如果只能做操作2, 答案就是第二类斯特林数$\left\{n\atop i\right\}$的前缀和 (对$i$从1加到$\min(k,n)$) 。出于后面的实现方便, 将对$i$从2加到$\min(k,n)$的前缀和记作$A(n)$。这可以用$O(n\log n)$的复杂度来求, 具体见oi-wiki

接下来考虑操作1。我们发现刚才找到的那些代表元当中有些可以经操作1生成, 现在来删除它们。将原型$arr$改写成连续的相同数个数的数组的形式, 记作$arr'$, 例如将$1,1,2,2,3$改写成$2,2,1$

  1. 如果$arr'$只有一个数, 就是说$arr$中全都是相同的数字, 我们发现$arr$一定可以由某个改写前有至少两个不同数的原型经一次操作1: $F(a, n)$生成, 于是不用对$arr$计数。也就是说, 题目中给的$k>1$时, 不用考虑这种情况。如果$k=1$, 输出1即可。
  2. 如果$arr'$不只有一个数, 去掉$arr'$的最后一个数, 考察前面的那些数。如果它们的$gcd$不为1, 则$arr$可以被别的原型由操作1生成, 不用对$arr$计数。对一个$gcd$, 有$A(\lceil {n\over gcd}\rceil)$个原型可以被别的原型$a$生成 (将$arr$中每连续$gcd$个数绑定, 再计算原型数, 也就是$A(\lceil {n\over gcd}\rceil)$) (注意$A$是从2开始加的, 因为数字全部相同的原型并不能由操作1生成$arr$) 。如果这个$gcd$是合数, 可能这些冗余数组会被它的因子删除多次, 需要控制这个次数, 解决方法是用mobius函数。就是说: 对$gcd$, 我们计$\mu(gcd)$$A(\lceil {n\over gcd}\rceil)$

这里的mobius函数就是在对$gcd$的质因子集合$S$做容斥: 质因子集合$S$的子集$S'\subset S$可以与那些各质因子至多出现一次的$gcd$的因子建立一一映射, 一个子集中有奇数个因子就取$-1$, 偶数个因子就取$1$, 有质因子出现2次就取0。子集为空集时 (对应于因子1) 也取1。

对一个给定的$gcd$, 那些能经操作1: $F(a, gcd)$生成的原型, 也可以被$gcd$的因子$d$们经操作1: $F(F(a,d), gcd/d)$生成。每个这样的原型被计了多少次呢? 答案是

$$\sum_{d|gcd}\mu(d)=\sum_{S'\subset S}(-1)^{|S'|}=\sum_{i=0}^{|S|}\binom{|S|}{i}(-1)^{i}\times 1^{|S|-i}=(-1+1)^{|S|}=[gcd=1] $$

也就是实现了, 若$arr'$除去最后一块外的所有数互质, $arr$就属于, 否则不属于, 这结束了我们的讨论。关于$0^0$不等式和$[gcd=1]$的讨论可以和Trie树维护集合相交性相类比。最后的答案是:

$$\sum_{gcd=1}^n\mu(gcd)A\left(\left\lceil\dfrac{n}{gcd}\right\rceil\right) $$

直接整除分块求这个东西的一个上界是

$$O(\sum_{gcd=1}^n\dfrac{n\log n}{gcd})=O(n\log n\sum_{d=1}^n\dfrac{1}{d})=O(n\log^2 n) $$

注意不是$O(n\sqrt{n}\log n)$。我们还可以合并同一个$\left\lceil\dfrac{n}{gcd}\right\rceil$对应的所有$\mu(gcd)$之和, 前缀和或者开桶统计一下就行。这时, 由于后面那个求和只有其中的$\sqrt{n}$项, 可能还达不到$\log n$, 可以理解为常数很小的$\log n$ (经测试, 对$n=10^5$该和为6.83) 。