题解：CF2039F2 Shohag Loves Counting (Hard Version)

来点考前题解。幽默的是场上以为 F2 就是 $\sum m\le 10^6$ 然后以为被卡常乐，鉴定为眼瞎导致的。最后六分钟意识到正确题意 rush 失败。

考虑某数在笛卡尔树上的子树大小 $s$，这意思是可以在 $1\sim s$ 的长度做贡献。由于 $f$ 两两不同，相邻的 $f$ 一定被不同的贡献，也就是说 $s_1,s_2\dots s_n$ 两两不同，也只能是 $1,2,\dots n$。易见此数组两两不同，因此 $n$ 长度数组的确定值域后的方案数是 $2^{n-1}$，这是因为次小值到最大值都可以随意选择放左侧/右侧。

现在只需对值域 dp 选了哪些。写成多步转移是 $f_{i,j}$，表示 $i\sim m$ 里面选的 gcd 是 $j$。转移为

这是 $O(m^2)$ 的（在 F1 中），考虑优化。注意到每次被影响的 $d=j$ 只有 $d\mid i$，枚举 $d$，使用莫反优化 dp。需要计算

若记 $F_x=\sum_{x\mid k}f_{i+1,k}$，则

暴力枚举 $t$，总复杂度为

每次更新 $f_{i,j}$ 后暴力更新 $F$，复杂度同上，可以通过 F1。

F2 需要从小到大 dp！易见转移是线性变换，那么记 $f=[0,0,0,\dots 0,1]$（$m$ 个 $0$），$A$ 为每次的转移矩阵，答案可以写为：

记 $f'=[1,1,1,\dots 1]$，转置之：

现在转移变成了 $(i,k)\to k$ 了，也类似地莫反转移即可（当然也可以直接转置掉 F1 的 dp）。