首先,我们考虑:数列 bbb 一定严格单调递减。
为什么呢?模了一个数 CCC 后,所得的 A′A'A′ 一定小于 CCC,接下来再用一个 D>CD>CD>C,发现 A′ mod D=A′A'\bmod D=A'A′modD=A′,没有任何意义。
因此,先将 aaa 从大到小排序。
而 n≤20n\le20n≤20,我们可以用二进制枚举。
即,用一个 nnn 位的二进制数,若第 iii 位为 111,则表示选中 aia_iai;否则表示不选中。
时间复杂度 O(nlogn+n⋅2n)O(n\log n+n\cdot 2^n)O(nlogn+n⋅2n)。
当然 dfs 也是可行的。
以下代码均为单测。
使用您的 Hydro 通用账户