题解

思路

方案只关心每个回文数使用多少次，不关心加数顺序，因此这是以所有不超过 $40000$ 的正回文数为面额的完全背包计数。

查询很多，应一次预处理整个范围。

做法

枚举 $1$ 到 $40000$，筛出十进制反转后不变的数。令 dp[0]=1。对每个回文数 $p$，按和从 $p$ 到 $40000$ 递增，执行 dp[sum]+=dp[sum-p] 并取模。最后每个查询直接输出 dp[n]。

外层枚举面额、内层递增枚举和，保证每种多重集合只按面额顺序被统计一次，同时允许同一面额重复使用。

正确性证明

处理完前若干个回文面额后，dp[s] 表示只使用这些面额组成 $s$ 的多重集合数。加入新面额 $p$ 时，原值统计不使用 $p$ 的方案，dp[s-p] 逐步包含使用任意多个 $p$ 的方案，添加一个 $p$ 后与前者互斥且完整。由面额归纳，最终 dp[n] 恰为全部回文数多重集合表示数。

复杂度分析

设回文数数量为 $P$，上界为 $N=40000$。预处理时间复杂度为 $O(PN)$，空间复杂度为 $O(N)$，每个查询 $O(1)$。

子任务说明

• 小范围可递归枚举各回文数使用次数。
• $t\le100,n\le1000$ 时可为每个查询单独做完全背包。
• 满数据离线预处理全部答案。