目前总分：100 + 100 + 50 + 0 + 8 + 0 + 50 = 308
A (100 pts)
\[f^k(x) = \dfrac{x^{2^k}}{2^{2^k-2}}=\left(\dfrac{x}{2}\right)^{2^k-2} \times x^2 \]当 \(x = 2\) 时，\(k\) 一定会很小就能 \(\geq 2^n\) 或无解。
当 \(x = 3\) 时：
\[\dfrac{x^{2^k}}{2^{2^k-2}} \geq 2^n \]\[x^{2^k} \geq 2^{n + 2^k - 2} \]\[\log_2 x^{2^k} \geq n + 2^k - 2 \]\[\log_b n = \dfrac{\log_a n}{\log_a b} \]\[\log_2 x^{2^k} = \dfrac{2^k}{\log_x 2} \]\[\dfrac{2^k}{\log_x 2} \geq n + 2^k - 2 \]\[2^k \geq n\log_x 2 + 2^k\log_x 2 - 2\log_x 2 \]\[2^k(1 - \log_x 2) \geq n\log_x 2 - 2\log_x 2 \]\[2^k \geq \dfrac{n\log_x 2 - 2\log_x 2}{1 - \log_x 2} \]\[\log_x 2 = \dfrac{\log_{10} 2}{\log_{10} x} \]直接通过 std :: log10 计算即可，期望 100 pts。
B (100 pts)
\[d_i = \lfloor1 + \log_{10} i\rfloor \]\[p_n = \sum_{i = 1}^{n}d_i \]\[\text{goal} = \sum_{i = 1}^{n}\varphi(i)(p_{\left\lfloor\frac{n}{i}\right\rfloor} + d_i \log_2 d_i) \]\(p\) 和 \(d\) 可以带 \(\log\) 以 一定常数 计算。
\(\varphi(x)\) 可以线性计算，期望 60 pts。
哦？最后一个 subtask 只需要跑 1.06s？
把 long long 换成 int，只需要 1.03s 了，卡常！
把 std :: vector 换成数组，一个点 1.03s 卡到 1.02s 了！
发现 \(d\) 函数调用了 \(2\) 次，改了改 0.919s 过了！100 pts！
C (50 pts)
直接暴力，期望 15 pts。
subtask 2 是简单的，就是 \(1 + 2 + \dots + n\) 减去 \(\left(1 + 2 + \dots + \left\lfloor\dfrac{n}{d}\right\rfloor\right) \times d\) 再加上 \(\left(1^2 + 2^2 + \dots + \left\lfloor\dfrac{n}{d}\right\rfloor^2\right) \times d^2\) 就行。
用 \(1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}\) 随便算算？
期望 30 pts。
\[1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2 \]\[1^4 + 2^4 + \dots + n^4 = \dfrac{n(n + 1)(2n + 1)(3n^2 - 3n + 1)}{30} \]知道了这些然后就可以容斥与 \(d\) 的 gcd 随便做做？期望可以过 subtask 4，50 pts。
D (0 pts)
\[D = \sum_{i = 1}^{n}d_i \]\[D' = \sum_{i = 1}^{n}d_i^2 \]\[V = \sum_{i = 1}^{n}v_i \]\[V' = \sum_{i = 1}^{n}v_i^2 \]\[\text{ESS} = \sum_{i = 1}^{n}(ad_i + b - v_i)^2 \]\[\text{ESS} = \sum_{i = 1}^{n}((ad_i - v_i)^2 + b^2 + 2b(ad_i - v_i)) \]\[\text{ESS} = b^2n + \sum_{i = 1}^{n}(ad_i - v_i)^2 + 2b\sum_{i = 1}^{n}(ad_i - v_i) \]\[\text{ESS} = b^2n + 2abD - 2bV + \sum_{i = 1}^{n}(ad_i - v_i)^2 \]\[\text{ESS} = b^2n + 2abD - 2bV + \sum_{i = 1}^{n}(a^2d_i^2 - 2ad_iv_i + v_i^2) \]\[\text{ESS} = b^2n + 2abD - 2bV + a^2D' + V' - 2a\sum_{i = 1}^{n}d_iv_i \]E (8 pts)
爆搜，期望 8 pts。
G (50 pts)
发现 10.in 的图是 \(n\) 个自环，是平凡的。答案是 \(420094585\)。期望 10 pts。
发现 4.in 的图是个 \(80\) 个点的完全图（含自环，共 \(80^2\) 条边），也就是可以随意走，边权都是 \(7\)，点权有 \(38\) 个 \(537653823\) 和 \(42\) 个 \(1\)。以及 \(V = 10^{13}\)
答案的公式为：
\[\sum_{i = 0}^{\left\lfloor\frac{10^{13}}{537653823}\right\rfloor}\dbinom{i+ 10^{13} - 537653823i}{i}7^{i + 10^{13} - 537653823i - 1} \times (38^i \times 42^{10^{13} - 537653823i}) \]\[\sum_{i = 0}^{18599}\dbinom{10^{13} - 537653822i}{i}7^{i + 10^{13} - 537653823i - 1} \times (38^i \times 42^{10^{13} - 537653823i}) \]对于任意的一个给定的 \(i\)，我们都可以在 \(\log 998244353\) 的时间内计算 \(7^{i + 10^{13} - 537653823i - 1} \times (38^i \times 42^{10^{13} - 537653823i})\)，所以考虑组合数怎么算。
\[\sum_{i = 0}^{18599}\left(\prod_{j = 1}^{i}\dfrac{10^{13} - 537653822i - j + 1}{j}\right)\left(7^{i + 10^{13} - 537653823i - 1} \times (38^i \times 42^{10^{13} - 537653823i})\right) \]哦，是不是可以 \(O(18599^2)\) 爆算啊？
真的可以，答案是 \(118356523\)，期望 20 pts。
看 5.in，这是限制了要走的步数，让你求路径权值和，显然可以矩阵快速幂！答案为 \(127395465\)。期望 30 pts。
看起来 1.in 的数据都挺小的，感觉很能 DP！答案为 \(286204592\)。期望 40 pts。
考虑 2.in。2.in 的边权都是 \(3\)，而且点权都不超过 \(400\)，还是可以矩阵快速幂。答案是 \(612200775\)。期望 50 pts。
标签：10,13,log,dfrac,sum,光芒,七道,照亮,pts From： https://www.cnblogs.com/RB16B/p/18133256