题解：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。转移为

f_{i,j}\gets f_{i,j}+2f_{i+1,k}(\gcd(k,i)=j<k)\\ f_{i,i}\gets f_{i,i}+1

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

\sum_k f_{i+1,k}[(k,i)=d]=\sum_{d\mid k}f_{i+1,k}[(\frac kd,\frac id)=1]\\ =\sum_{d\mid k}f_{i+1,k}\sum _{t\mid (\frac kd,\frac id)}\mu (t)\\ =\sum _{t\mid \frac id}\mu (t)\sum_{dt\mid k}f_{i+1,k}

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

=\sum _{dt\mid i}\mu (t)F_{dt}

暴力枚举 t，总复杂度为

\sum_{i\mid j\mid k\le m}=O(m\log^2m)

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

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

ans=\sum_i (fA_m A_{m-1}A_{m-2}\dots A_1)_i

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

ans=(f'A_1^TA_2^T\dots A_m^T)_{m+1}

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