时光过去的好快啊。感觉去年那个在酒店里自闭地写完 2018 总结的我就在不久之前。这一年,我个人各方面都得到了或多或少的改变。
时光过去的好快啊。感觉去年那个在酒店里自闭地写完 2018 总结的我就在不久之前。这一年,我个人各方面都得到了或多或少的改变。
刚开始看到分治的标签就下定决心用分治做,没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。
首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案,那么我们往左的时候可以合并之,并设置\(nxt[i]\)来进行跳跃;由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG,所以我们可以使用类似 AC 自动机的方式用 Map 合并信息:交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。
首先,需要学习最值反演和二项式反演,式子如下:
\[ \max(S) = \sum_{T \subset S} (-1)^{|T| – 1} \min(T) \\ f_i = \sum_{j = 0}^i {i \choose j} g_j \Leftrightarrow g_i = \sum_{j = 0}^i (-1)^{i – j} {i \choose j} f_j \]
然后,你需要对反演和容斥有一定的理解,能理解容斥系数的意义。
记公式:
Or operation: arr[k + step] += opt * arr[k] And operation: arr[k] += opt * arr[k + step] Xor operation: A = arr[k], B = arr[k + step] arr[k] = A + B, arr[k + step] = A - B with inverse-operation, the inv2 is needed: arr[k] /= 2, arr[k + step] /= 2;
这算是广义后缀自动机的一个通用(general)运用。我们可以像统计多个串一样来做这个,只不过我们需要在树上 DFS 时记录分岔点的 SAM 节点,然后进行回溯。剩下计算本质不同字串个数的方法就很套路了。
先写出答案的式子:
\[ \prod_{i = 1}^n \prod_{i = 1}^m f(\gcd(i, j)) \]
老套路,枚举公约数:
\[ \prod_{d = 1}^{\min(n, m)} f(d)^{\sum_{i = 1}^n \sum_{j = 1}^m [gcd(i, j) = d]} \]