关于「一道简单的数数问题」

这道题原题其实是 IMO 美国队训练题集中的一道题……

不过这也并不代表我水平多高什么什么的，只是这么说的话你会更有兴趣看完。看完你就知道为什么我会知道这道题了。

首先抛开事实不谈，以一个 OIer 的角度审视这道题。

很容易得出穷举法，时间复杂度 。

仔细思考一下，用一个数组 记录状态 和子集和除以 余数，就得到了线性 DP 做法，时间复杂度 。

再仔细思考一下，矩阵快速幂一优化我们就得到了 做法。

继续思考就不是我能在这跟你讲的了，请看 B 站（没错我就是从这里知道的这道题）BV1R34y1W7Xn。

题目以高中数学视角看还是可以理解绝大部分的，放心食用。

至于这道题为什么没数据，这是因为我是个懒狗，只是在以一个退役 OIer 的身份分享一下可能有价值的题。如果有大佬可以完善一下的话鄙人感激不尽。

（另外数据范围也是瞎定的，建议如果有人要完善好这道题的话把它重新划定一下）

（另外一提，部分分思路抄的 B 站评论区）