喵哈喽~！各位算法大师们，你们好呀！咱是乃爱算法的小猫娘 Nyaatra~！今天咱要和大家一起玩一个有趣的数字游戏，就是 Codeforces 上的 1673C 题，叫做“回文基数”喵！(ฅ'ω'ฅ)
这个问题就像是把一堆闪闪发光的宝石（回文数）放进一个盒子里，让它们的总重量恰好等于 n，我们要数一数总共有多少种放法，听起来是不是很有趣呀？那么，就让咱带大家一起来看看怎么解决这个难题吧！
题目大意
首先，我们来理解一下题目的要求是什么喵~
题目会给我们一个正整数 n。我们需要找到，有多少种不同的方法可以将 n 表示成一堆正回文数的和。
- 什么是回文数呢？ 就是一个正着读和反着读都一样的数字，比如
5,121,3443都是回文数，但是10,12就不是啦。 - 什么是不同的方法呢？ 题目里说，只要每种回文数使用的数量不一样，就算作不同的方法。比如，对于
n=5：5 = 3 + 1 + 1和5 = 1 + 3 + 1被认为是同一种方法，因为它们都用了 1 个3和 2 个1。5 = 4 + 1和5 = 3 + 1 + 1就是不同的方法，因为第一种用了4和1，第二种用了3和1，使用的回文数种类和数量都不同。
简单来说，就是把 n 分解成若干个回文数的和，求分解方案数。因为答案可能会很大，所以需要对 10^9 + 7 取模。
解题思路 (ฅ'ω'ฅ)
看到这个问题，咱的猫猫直觉告诉咱，这很可能是一个动态规划（DP）问题！为什么呢？因为它要求“方案数”，而且一个大问题的解可以由小问题的解推导出来。
这个问题其实是一个经典的组合问题，可以转化成我们非常熟悉的完全背包问题！
- 背包的容量 (Knapsack Capacity): 就是题目给定的目标和
n。 - 物品 (Items): 就是所有小于等于
n的正回文数。比如1, 2, 3, ..., 9, 11, 22, ...等等。 - 物品的重量 (Item Weight): 每个回文数
p的“重量”就是它本身的值p。 - 物品的价值 (Item Value): 在这里我们不关心价值，我们只关心方案数。可以认为每个物品的价值都是 1。
- 问题转化: 求用这些可以无限次使用的“物品”（回文数），恰好装满容量为
n的“背包”的方案总数是多少？
这不就是完全背包问题的模板了嘛！
于是，我们的解题步骤就清晰了喵：
- 预处理： 先把所有
1到40000之间的回文数都找出来，存起来当我们的“物品列表”。因为题目中n的最大值是40000，所以我们只需要处理到这个范围就行啦。 - 动态规划：
- 我们创建一个 DP 数组，
dp[i]表示凑成数字i的方案数。 - 状态定义:
dp[i]代表将i表示成回文数之和的方案数。 - 初始化:
dp[0] = 1。这是个很重要的基础！因为凑成 0 的方案只有一种，就是什么都不选。 - 状态转移: 我们遍历每一个回文数
p（我们的物品），然后用它来更新 DP 数组。对于从p到n的每一个j，我们都可以通过在凑成j-p的方案上再加一个p来得到凑成j的新方案。所以状态转移方程就是：dp[j] = (dp[j] + dp[j - p]) % MOD
- 我们创建一个 DP 数组，
因为题目有多组测试数据，而 n 的范围是固定的，所以我们可以先把 1 到 40000 的所有 dp 值都计算出来。这样，对于每个查询，我们就可以直接输出 dp[n] 的值，非常快，喵~！
代码题解
下面就是这份思路的 C++ 实现啦，咱在代码里加了一些注释，方便大家理解每一部分在做什么哦！
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
// 定义常量喵
const int MAX_N = 40000;
const int MOD = 1000000007;
// 全局的 DP 表和回文数列表
// precompute() 函数会把它们填满
std::vector<int> dp(MAX_N + 1, 0);
std::vector<int> palindromes;
// 检查一个数是不是回文数的函数
// 一个数是回文数，如果它的字符串表示正反都一样，nya~
bool is_palindrome(int n) {
std::string s = std::to_string(n);
std::string reversed_s = s;
std::reverse(reversed_s.begin(), reversed_s.end());
return s == reversed_s;
}
// 预处理函数，在处理测试用例前只调用一次
void precompute() {
// 1. 生成所有小于等于 MAX_N 的回文数
// 我们要把所有能用的“宝石”（回文数）都收集起来！
for (int i = 1; i <= MAX_N; ++i) {
if (is_palindrome(i)) {
palindromes.push_back(i);
}
}
// 2. 动态规划，计算凑成每个数的方案数
// 这就是完全背包问题的核心部分啦
// dp[i] 会存储把 i 表示成回文数之和的方案数
// 基础情况：凑成 0 的方案有 1 种（什么都不选）
dp[0] = 1;
// 遍历我们收集到的每一种回文数“宝石”
for (int p : palindromes) {
// 更新 DP 表，对于所有能用上 p 的 j
for (int j = p; j <= MAX_N; ++j) {
// 凑成 j 的方案数，等于原来的方案数，
// 加上“在凑成 j-p 的方案上再加一个 p”的方案数
dp[j] = (dp[j] + dp[j - p]) % MOD;
}
}
}
// 解决单个测试用例的函数
void solve() {
int n;
std::cin >> n;
// 答案我们已经提前算好啦，直接从 DP 表里拿出来就行
std::cout << dp[n] << "\n";
}
int main() {
// 快速输入输出，让程序跑得更快一点~
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// 进行一次预计算
precompute();
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}知识点介绍：完全背包问题
这道题的核心就是完全背包问题求方案数的变种。让咱来详细讲讲这个知识点吧，喵~
什么是完全背包问题？
标准定义是：有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包，可使这些物品的耗费的总重量不超过背包容量，且价值总和最大。
和本题的联系
我们的问题不是求最大价值，而是求恰好装满背包的方案数。
- 物品： 所有回文数
p。 - 物品重量：
p本身。 - 背包容量：
n。 - 目标： 求恰好装满容量为
n的背包，有多少种不同的装法。
DP 状态与转移
状态定义：
dp[j]：表示装满容量为j的背包的方案总数。初始化：
dp[0] = 1。这是关键！容量为 0 的背包只有一种装法，就是什么都不装。所有后续的计算都基于这个初始状态。其他的dp[j](j>0) 初始化为 0。状态转移方程： 对于第
i个物品（重量为w[i]），当我们考虑如何装满容量为j的背包时，可以有两种选择：- 不放第
i个物品：方案数来自之前的结果，即dp[j]的旧值。 - 放第
i个物品：这意味着我们从容量为j-w[i]的背包状态转移而来，方案数为dp[j-w[i]]。
所以，总的方案数是这两种选择的方案数之和。当我们用循环实现时，这个过程可以简化为：
dp[j] = dp[j] (不放第 i 个物品的方案数) + dp[j - w[i]] (放第 i 个物品的方案数)写成代码就是：
cpp// 遍历物品 for (int p : palindromes) { // 遍历背包容量 for (int j = p; j <= MAX_N; ++j) { dp[j] = (dp[j] + dp[j - p]) % MOD; } }这里有一个小细节：为什么内层循环
j是从小到大（正序）的？- 正序循环（完全背包）： 当我们计算
dp[j]时，dp[j-p]已经是被当前物品p更新过的状态。这意味着dp[j-p]可能已经包含了物品p。所以dp[j-p]再加上一个p得到dp[j]，就实现了“物品p可以使用多次”的效果。 - 倒序循环（0/1背包）： 如果内层循环是从大到小，那么在计算
dp[j]时，所用到的dp[j-p]还是上一轮（处理前一个物品时）的结果，没有被当前物品p更新过。这就保证了每个物品最多只被使用一次。
- 不放第
所以，通过这个小小的循环方向的差异，我们就能区分开完全背包和 0/1 背包啦！是不是很奇妙呢？喵~
好啦，今天的题解分享就到这里啦！希望大家都能理解并掌握完全背包这个强大的工具！如果还有什么问题，随时可以再来找咱玩哦！Nya~ (ฅ^•ﻌ•^ฅ)