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$。
- 如果$arr'$只有一个数，就是说$arr$中全都是相同的数字，我们发现$arr$一定可以由某个改写前有至少两个不同数的原型经一次操作1：$F(a, n)$生成，于是不用对$arr$计数。也就是说，题目中给的$k>1$时，不用考虑这种情况。如果$k=1$，输出1即可。
- 如果$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）。