题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。

每组数据输入$n(1 \leq n \leq 4 \times 10^4)$。

输出把$n$拆分成若干回文数之和的方案数。结果可能很大，对结果模上$10^9+7$。

例如$3$有$3$种方案：$3$，$2+1$，$1+1+1$。

输入样例

2
5
12

输出样例

7
74

算法

完全背包求方案数

这个题可以先预处理出$4 \times 10^4$范围内的所有回文数，存入$a$数组中。结果发现只有不到$500$个，那就可以利用完全背包来求方案数，相当于从$a$中选数，每个数的个数没有限制，使得刚好凑出数$n$的方案数。

边界条件是$f[0]=1$，表示$0$有一种拆分方案。外层循环遍历$i \in [1,m]$，其中$m$表示$[1,4 \times 10^4]$内回文数的个数。内层循环遍历$j \in [a[i],n]$，使用完全背包优化掉第一维的技巧，状态转移方程为

$f[j]=f[j]+f[j-a[i]]$

最后的答案就是$f[n]$。

复杂度分析

时间复杂度

考虑到有多组测试用例，可以先在整个数据范围$[0,4 \times 10^4]$上进行动态规划，时间复杂度为$O(mn)$。然后$t$个查询直接$O(1)$查表即可，整体的时间复杂度为$O(mn+t)$。

空间复杂度

空间瓶颈在于DP数组$f$，它的规模是$O(n)$的，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 40010, MOD = 1e9 + 7;
int t, n, f[N], a[500];

int rev(int x) {
    int res = 0;
    while(x) {
        res = 10*res + x%10;
        x /= 10;
    }
    return res;
}

int main() {
    scanf("%d", &t);
    int m = 0;
    for(int i = 1; i <= N - 10; i++) {
        f[i] = 0;
        if(i == rev(i)) {
            a[++m] = i;
        }
    }
    f[0] = 1;
    for(int i = 1; i <= m; i++) {
        for(int j = a[i]; j <= N - 10; j++) {
            f[j] = (f[j] + f[j - a[i]]) % MOD;
        }
    }
    while(t--) {
        scanf("%d", &n);
        printf("%d\n", f[n]);
    }
    return 0;
}