20PTS
深搜,参考下面的代码.
对于每次查询,时间复杂度:O(3N)O(3^N)O(3N).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
40PTS
我们发现前四个测试点答案也就不超过 151515 种,考虑记忆化.
对于每次查询,时间复杂度:O(1)O(1)O(1) 或 O(3N)O(3^N)O(3N).
总时间复杂度:O(3N)O(3^N)O(3N).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
100PTS
既然最终答案能记忆化,那能不能每个过程都记忆化一遍呢?
我们可以记录第 iii 位每种 357357357 出现情况的种类数,分类讨论.
将 357357357 都出现的情况记作 AAA,将 357357357 出现两个的情况记作 BBB,将 357357357 出现一个的情况记作 CCC.
AAA:
1. 可以由上一个 AAA 填上 3,5,73,5,73,5,7 获得,情况数 ×3\times 3×3.
2. 可以由上一个 BBB 填上所缺的数获得.
BBB:
1. 可以由上一个 BBB 填上 3,5,73,5,73,5,7 中的两个数字获得,情况数 ×2\times 2×2.
2. 可以由上一个 CCC 填上所缺的数获得.
CCC:
可以由一个都没有获得.
对于每次查询,时间复杂度:O(1)O(1)O(1).
预处理时间复杂度:O(N)O(N)O(N).
总时间复杂度:O(N)O(N)O(N) .
如果你嫌内存占用太大了,你可以多花费 O(TlogT)O(T\log T)O(TlogT) 的时间复杂度转离线,把空间复杂度降至 O(1)O(1)O(1).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
120PTS
Macw老师提出来一个快速的办法,理论上可以通过 T=1,N≤10107T=1,N\le 10^{10^7}T=1,N≤10107 的数据!
首先是随便选取 357357357 中的任意一位,总共有 3N3^N3N 种情况.
然后减去只选择两个数的,即只选 353535 的,只选 373737 的和只选 575757 的,共有 3×2N3\times 2^N3×2N 种情况.
我们发现只选一个数的情况多选了一次,所以需要加回,即将结果 +3+3+3.
这样就可以以 O(logN)O(\log N)O(logN) 的时间复杂度求出答案了!
我们注意到 109+710^9+7109+7 与 2,32,32,3 均互质,所以对于更大的数可以用费马小定理来将 NNN 降至 109+510^9+5109+5 以内.
对于每次查询,时间复杂度:O(logN)O(\log N)O(logN) .