脚本宝典收集整理的这篇文章主要介绍了「AHOI2022」山河重整 解题报告，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
给定整数集合 (S={1,...,n}), 计算有多少个子集 (Tsubseteq S), 使得 (1,2,dots,n) 都可以被表示为 (T) 的一个子集中所有数的和. (nle 5times 10^5), 答案对 (M) 取模.
设 (a_{k+1}) 计数和为 (k), 且可以表达出 (1,dots,k) 的集合数量. 由于每个集合存在最小的不可表示之数, 得到生成函数方程
而答案就是 (displaystyle 2^n - sum_k a_k 2^{n-k}).
若进行倍增转化只需解决给定一组 (a_k), 计算
的问题.
注意到 (displaystyle (1+x^k)(1+x^{k+1})cdots = sum_{jge 0}frac{x^{j(j-1)/2+jk}}{(1-x)cdots(1-x^j)}), 原恒等式的 LHS 可以展开成
因此我们有
右式可以 (j) 从大到小合并, 复杂度为 (O(n^{3/2})).
Remark 1 有人认为 集合里只用考虑加入了 (O(sqrt n)) 个数 是本题的一个关键的切入点, 但这个性质是不重要的. 我们知道, 整数拆分有 Durfee Square 分解, 适当调整题意将问题改成类似的拆分问题 (例如每个数可以出现任意多次) 仍然可以有类似的 (O(n^{3/2})) 算法, 从整数拆分的 (O(n^{3/2})) DP 的角度也有此结论.
Remark 2 如许使用 FFT, 我们能做得更好: 我们将 (A(x)) 的前 (b) 项和后面的项分开处置, 前面的项可以写作
通过分治 FFT 可以在 (O(b^2log^2n)) 时间内计算.
后面的项按照原来的方法处理, 复杂度是 (O(n^2/b)).
平衡复杂度为 (O(n^{4/3} log^{2/3} n)).
Question 1: 是否存在 (n) 上指数更低的算法? 不过相关问题的思考表明, (tilde O(n^{4/3})) 可能也是一个相当典型的构造. 此外, 也有一些更奇怪的问题可以做到 (tilde O(n^{5/4})), 不太确定其思想能否派上用场.
Remark 3 本题的另一个扩展方向是变成输入的整数拆分, 比如将一开始的整数集合 (S) 从给定的一个很规则的集合改为输入. 但这一方面当时似乎只得到了类似 (tilde O(n^{3/2})) 的平凡结果, 实现也颇为笨重, 故没有进一步探索.
以上是脚本宝典为你收集整理的「AHOI2022」山河重整 解题报告全部内容，希望文章能够帮你解决「AHOI2022」山河重整 解题报告所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。