P8740 题解

ikunTLE · 2024-11-20 22:10:30 · 题解

题目传送门

问题 A

定义一个桶，每一次循环将 0 到 9 放入桶中，直到桶的某个值 \ge2019，结束程序并输出循环次数。

答案：3181。

问题 B

建立一个平面直角坐标系，求出直线的函数。随后求出斜率，枚举并用 set 去重。

答案：40257。

问题 C

首先将 n 分解质因数，将其存入序列 A，并计算 A_i\times A_j\times A_k=n 的数量。

答案：2430。

问题 D

首先根据题意模拟建图。由于是提交答案题，用时间复杂度为 \mathcal{O}(n^3) 的 Floyd 算法跑一遍也是可以接受的。

答案：10266837。

问题 E

状压 DP。设 S 为到达 i 时的排列，j 为到达 j 时的方案数，则状态转移方程为：

答案：881012367360。