题目

原题链接

问题描述

如果一个不含前导0的正整数翻转后值不发生改变，那我们就称这个数为回文数。
一个数$n(1\le n\le 4\ast 10^4)$可以由若干个回文数之和来表示，问对于$n$来说总共有多少不同的回文数表示方法。
若两种表示方法仅顺序不同，仍然视作相同的表示，如$3=2+1=1+2$.

分析

由于数据范围不算大，只有$4\ast 10^4$，我们可以直接暴力枚举出所有的回文数，共计$498$个。
可以参考完全背包的写法，完全背包给定物品的体积和价值，求目标容积下的最大价值。

以$dp[n][m]$表示使用前$n$个物品下总体积为$m$的方法数,$a_n$表示第$n$个物品的体积：
$dp[n][m]=dp[n-1][m]+dp[n][m-a_n]$
通过观察，发现可以进行一维空间优化：
$dp[m]=dp[m]+dp[m-a_n]$

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define fir(i, a, b) for (ll i = (a); i <= (b); i++)
#define rif(i, a, b) for (ll i = (a); i >= (b); i--)
const int N=4e4;
vector<ll>a;
ll dp[N+5];
ll mod=1e9+7;
bool f(ll x){vector<ll>tmp;while(x){tmp.push_back(x%10);x/=10;}ll sz=tmp.size();if(sz==1)return true;fir(i,0,sz-1){if(tmp[i]!=tmp[sz-1-i])return false;}return true;
}
inline void solve(){ll n;cin>>n;cout<<dp[n]<<endl;
}
int main(){fir(i,1,N){if(f(i))a.push_back(i);}dp[0]=1;ll sz=a.size();fir(i,0,sz-1){for(int j=a[i];j<=N;j++){dp[j]=(dp[j]+dp[j-a[i]])%mod;}}ll _;cin>>_;
//	_=1;while(_--){solve();}return 0;
}