2024.11.5
-
-
顶括号的整除分块：有一个与底括号类似的结论，即若区间的整除值为 \(x\)，则区间的左端点 \(l = \lceil n/x \rceil\)。
-
题解中给了另外一种做法，如果对每个不同的除数都只计算一次贡献，那么就可以在 \(O(V \ln V * \log_2 V)\) 的时间复杂度内解决。
当时做这道题的时候不知道为什么大样例的行末出现了空格。。。然后有点武断了，肉眼比对过了大样例就没有管，其实这时候的正确选择是自己对拍一下。
-
-
-
说来离谱。我在平凡 \(O(nm^2)\) DP 的基础上加了一个卡常优化就过了。具体的复杂度分析如下：
\[\sum_{i=1}^n \sum_{j=i}^{m-n+i} \sum_{k=i}^j 1 = \sum_{i=1}^n \sum_{j=1}^{m-n+1} j = \dfrac{1}{2}n(m-n+2)(m-n+1) = \dfrac{1}{2}(n^3 - (2m+3)n^2 + (m^2+3m+2)n) \]
-