[OI题解] P10788 [NOI2024] 分数

$\text{Difficulty : CF3300 | (7)}$

$\text{Quality : A-}$

观察到每一个答案 $(a,b)$ 都存在唯一的回归到 $(1,0)$ 的方式:

若 $b<a$ 则回归到 $(b\mathrm{mod}(2a),a)$，否则回归到 $(a,b)$，这种类似欧几里得变换的过程可以将每个 $(a,b)$ 唯一对应一条从 $(1,0)$ 变化而来的路径。

于是我们从 $(1,0)$ 开始可以以搜索树状遍历每个完美分数集合中小于 $1$ 的分数，且答案仅被遍历一次。 大于 $1$ 的可以同理统计，时间复杂度 $O(ans)$，可以得到 $90$ 分。

观察到 $ans$ 不是特别大，考虑时间复杂度就是直接和 $ans$ 相关的做法。

我们考虑形式化这个搜索的过程，该过程形如对二元组 $(u,d)$ 进行 $a_i$ 次 $d\leftarrow d+2u$ 后交换 $u,d$，那么序列 $a_i$ 与每个小于 $1$ 的完美分数唯一对应。

直接枚举所有 $a_i$ 序列太低效了，我们尝试枚举一部分，统计另一部分。

假设现在已经经历了序列 $a_1\dots a_{i-1}$ 得到了二元组 $(u,d)$，下一步会得到二元组 $(d,u+2d\times a_i)$，然后接下来每一步都是让 $d\leftarrow d+2u$ 后交换 $u,d$，分子分母始终是关于 $a_i$ 的一次函数，故我们带着这个一次函数继续搜索下去，这样可以在结束位置是统计 $k_1{a}_i+b_1\le n$，$k_2{a}_i+b_2\le m$ 的 $a_i$ 的个数即可减少一层搜索暴力枚举的时间。

你可以尝试枚举其它位置，统计第一位或者任何某一位，但是无论统计确定的哪一位，几乎不能将状态量减少到可以接受的级别。

于是我们尝试聪明地枚举值较小的位置，统计最大的 $a_x$ 可能的取值，这样可以一次统计尽可能多的序列，为我们节省更多的枚举。

经测试，该状态数小于 $10^8$，在本题时限下可以接受。

具体实现可以考虑先搜索 $(u,d)$ 并记录其对应的 $a_i$ 的最大值，然后尝试在该位钦定为序列 $a_i$ 的首个最大值，设其为 $x$，然后记录 $u,d$ 关于 $x$ 的 $kx+b$ 的形式，然后统计时可以 $O(1)$ 统计 $x>mx$ 且 $k_{1}x+b_1\le n$，$k_{2}x+b_2\le m$ 的 $x$ 即可。

代码

注意剪枝保证复杂度减少无效统计。