C. Palindrome Basis - DP

C. Palindrome Basis

https://codeforces.ml/contest/1673/problem/C

题意

给你一个数 问你一共有多少种不同的组合 可以实现若干个回文数字相加得到这个数

思路

数据不超过4e4 而对于4e4之内的回文数字 最多不超过500 （一位数回文数有9个 两位的9个 三位的90个 四位的90个 5位的有300个 一共就489个）
4e4+500的复杂度可以被接受
可以转换为简单的dp
dp[i][j] 代表数字i 只由前j个回文数组合的方法数
那么转移方程就可以是： $$dp[i][j] = dp[i - pa[j]][j] + dp[i][j - 1]$$

#include
#include
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
 
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const int N = 4e4 + 10;
const int M = 1e5 + 5;
const int mod = 1e9 + 7;
ll n, m, dp[N][505], pa[40010];
//判断是否为回文串 
bool isp(ll x) {
	ll xx = 0, nn = x;
	while (x > 0) {
		xx = x % 10 + xx * 10;
		x /= 10;
	}
	if (xx == nn) return true;
	else return false;
}
 
void solve()
{
	cin >> n;
	cout << dp[n][500] << "\n";
}
 
signed main()
{
	IOS;
	ll tot = 0;
	for(int i = 1; i <= 40005; i++){
		if (isp(i)) pa[++tot] = i;
    }
	for (int i = 1; i <= 500; i++) {
		dp[0][i] = 1;//开始初始化 
	}
	for (int i = 1; i <= 40005; i++) {//遍历所有数
		for (int j = 1; j <= 500; j++) {//遍历用到回文数的个数
			if (pa[j] <= i) dp[i][j] = (dp[i][j - 1] + dp[i - pa[j]][j]) % mod;
			else dp[i][j] = dp[i][j - 1];
		}
	}
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}