p709: O(n^2) dp, 比较容易想到。
p708: 求一类积性函数的前缀和，有空尝试一下写 Min_25 筛。
p707: 看了一会没啥思路…然后搜了大半小时 paper 和资料，搜到了 Light Out 这个网站…可能还需要理解一些概念…
p706: 四维 dp。
p705: 一开始理解错题了…inversion count 显然就是计算逆序对，divided sequence 就是序列中每个数字的因子数乘积。预处理每对数字对 inversion count 的贡献，然后暴力所有质数并记录数字的频率，用乘法原理统计答案即可。
p704: 和 Kummer’s theorem 有关…
p703: 树形 dp，计算独立集。
p702: 建坐标系，发现规律，二的幂次相关，range-counting 类问题。$O(nlogn)$。可以做到 $O(logn * logn)$…这可太难了…
p547: 求带洞的正方形中任意两点间距离的期望，从 wuhang 在 p695 的 post 里学了一下拟蒙特卡罗(quasi-Monte Carlo)然后做的…
p539: 找规律。$P(2k)=P(2k+1)=2k-2P(k)+2$, $S(2k)=2k^2+4k-1-2P(k)-4S(k-1)$, $S(2k+1)=2k^2+6k+1-4S(k)$。
p487: 多项式及其求和。其实就是伯努利多项式。然后看到 Min_25 将它推广了…搞了个任意模数 NTT….学不来…
p479: 韦达定理…等比数列求和…
p476: Malfatti circles, 贪心，只有一种放法可以使得面积最大，但我不会证明…不过有 paper 证明了…
p475: dp….看到可以将题目转化为图的计数的神奇做法…
p442: 二分 + AC 自动机上DP…
p441: 莫比乌斯反演, 那个求和只要差分一下就变成调和级数了。 $O(nlogn)$。可以做到 $O(n^{2/3} (\log n)^{1/3})$。
p430: 第 $i$ 个盘子没有被翻转的概率是 $p = \frac{(i - 1)^2 + (N - i)^2}{N^2}$，$prob(k)$ 表示在 $k$ 轮后白面向上的盘子数目的概率。$prob(k) = prob(k - 1) * p + (1 - prob(k - 1)) * (1 - p)$ => $prob(k) = \frac{1 + (2q - 1)^k}{2}$，显然，计算 $(2q - 1)^m$ 时，让 $(2q - 1)^m$ 足够小即可。那么答案就是 $\frac{n}{2} + \sum_{k=1}^n {prob(k)}$。
p417: 可以发现，$L(k) = L(k * 2), L(k) = L(k * 5)$, 其中，$k \mod 2 = 0$ or $k \mod 5 = 0$。 $L(k) = x$, 满足最小正整数 $x$, $10^x \mod k = 1$ && $phi(k) \mod L(k) = 0$。时间复杂度：$O(nlog^2 n)$。
p343: 可以发现，$f(k) = largest\_prime\_factor(k+1)-1$, $k^3 + 1 = (k + 1) * (k^2 - k + 1)$, $f(k^3) = largest\_prime\_factor(k^3+1)-1$ => $largest\_prime\_factor((k + 1) * (k^2 - k + 1))-1$ => $max(largest\_prime\_factor(k + 1), (k^2 - k + 1)) - 1$。
p333: dp。$dp[i][j]$ 表示对于 $i$ 可以满足 $i = \sum_{}{2^x3^y}$ 的 partition 的个数，其中， $y <= j$。所以 $j$ 的上限是 $log_3{1000000}$。
p317: 物理题. 考虑两种最极端的情况: (1) 垂直向上射出, 可以算出一个最高点。 (2) 水平射出, 可以算出一个最远点。连接这两个点就是一条抛物线，求这个抛物线的包络线就可以了。需要花时间 re-learn 一下以前简单的物理公式，然后直接推导出公式即可。抛物线体的体积计算：Paraboloid。高中物理里的斜抛物体最高上升高度 $h=\frac{v^2}{2g}$。
p303: 简单的 bfs。用 python 写会很慢(用 list 实现 queue)，加了剪枝才快，不加剪枝很慢，换成 C++ 不加剪枝都很快…因此建议用 C++ 写，但是 $f(9999)$ 爆 long long 了。这个甚至可以直接 OEIS。
p297: 找规律，A007895。可以发现一些递归结构。需要记忆化。$z(m) = z(f(n)) + z(m-f(n)) + m-f(n)$, $f(n)$是小于 $n$ 中最大的 fibonacci number。
p288: 直接根据阶乘的中质因子 $p$ 的个数的公式计算。$p^n!$ 的 质因子 $p$ 的个数是 $\frac{p^n - 1}{p - 1}$
p226: Simpson 积分…
p200: Miller-Rabin…暴力…
p178: 四维dp。
p162: 容斥原理直接手算….发现 MuthuVeerappanR 这人就喜欢啥题都用生成函数去做…还有人将 16 个数字推广到 n 个数字的…
p160: 找出 $10^{12}!$ 的最后非零五项。中国剩余定理 或者 利用 last5Digit($n$) = last5Digit($n * 5^x$) 即，last5Digit($10^{12}$) = last5Digit($2560000$) 或者 wolframalpha。
p159: dp。递推式: $mdrs(n) = max(drs(n), mdrs(a) + mdrs(b))$, $a * b == n$。
p158: 对于每个 $n$, 答案就是 Eulerian_number, $A(n, 1) = 2^n-n-1$, 因此, $p(n)=(2^{n}-n-1)\binom{26}{n}$
p157: 简单推导变换后，暴力枚举+分解质因数
p156: $f(n, d)$ 的数位dp + 剪枝
感谢阅读
Thanks
-
Welcome！