C. Palindrome Basis
题意
定义一个正整数 a a a 是回文的(没有前导 0 0 0)当且仅当: a a a 的十进制表示形式回文
给定一个正整数 n n n ,求出将 n n n 拆分成若干个回文数之和的方案数
思路
这是一个经典模型,与爬楼梯问题不同的是:这道题一个物品的选择先后顺序无关
在 n ≤ 4 ⋅ 1 0 4 n \leq 4 \cdot 10^4 n≤4⋅104 时,求出回文数字共有 498 498 498 个,考虑 D P DP DP:
用 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示只使用前 j j j 个回文数字来构成 i i i 的方案数,那么转移为:
d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + d p [ i − P [ j ] [ j ] , P [ j ] ≤ i dp[i][j] = dp[i][j-1] + dp[i - P[j][j],P[j] \leq i dp[i][j]=dp[i][j−1]+dp[i−P[j][j],P[j]≤i
意思就是:不用第 j j j 个回文数字 加上 使用 P [ j ] P[j] P[j] 的方案数。
初始化: ∀ j ∈ [ 1 , 498 ] , d p [ 0 ] [ j ] = 1 \forall j \in [1,498],dp[0][j] = 1 ∀j∈[1,498],dp[0][j]=1
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;
const int INF=0x3f3f3f3f;
const long long INFLL=1e18;
typedef long long ll;
template<class T>
constexpr T power(T a, ll b){
T res = 1;
while(b){
if(b&1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
constexpr ll mul(ll a,ll b,ll mod){
//快速乘,避免两个long long相乘取模溢出
ll res = a * b - ll(1.L * a * b / mod) * mod;
res %= mod;
if(res < 0) res += mod; //误差
return res;
}
template<ll P>
struct MLL{
ll x;
constexpr MLL() = default;
constexpr MLL(ll x) : x(norm(x % getMod())) {
}
static ll Mod;
constexpr static ll getMod(){
if(P > 0) return P;
return Mod;
}
constexpr static void setMod(int _Mod){
Mod = _Mod;
}
constexpr ll norm(ll x) const{
if(x < 0){
x += getMod();
}
if(x >= getMod()){
x -= getMod();
}
return x;
}
constexpr ll val() const{
return x;
}
explicit constexpr operator ll() const{
return x; //将结构体显示转换为ll类型: ll res = static_cast<ll>(OBJ)
}
constexpr MLL operator -() const{
//负号,等价于加上Mod
MLL res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLL inv() const{
assert(x != 0);
return power(*this, getMod() - 2); //用费马小定理求逆
}
constexpr MLL& operator *= (MLL rhs) & {
//& 表示“this”指针不能指向一个临时对象或const对象
x = mul(x, rhs.x, getMod()); //该函数只能被一个左值调用
return *this;
}
constexpr MLL& operator += (MLL rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLL& operator -= (MLL rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLL& operator /= (MLL rhs) & {
return *this *= rhs.inv();
}
friend constexpr MLL operator * (MLL lhs, MLL rhs){
MLL res = lhs;
res *= rhs;
return res;
}
friend constexpr MLL operator + (MLL lhs, MLL rhs){
MLL res = lhs;
res += rhs;
return res;
}
friend constexpr MLL operator - (MLL lhs, MLL rhs){
MLL res = lhs;
res -= rhs;
return res;
}
friend constexpr MLL operator / (MLL lhs, MLL rhs){
MLL res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream& operator >> (std::istream& is, MLL& a){
ll v;
is >> v;
a = MLL(v);
return is;
}
friend constexpr std::ostream& operator << (std::ostream& os, MLL& a){
return os << a.val();
}
friend constexpr bool operator == (MLL lhs, MLL rhs){
return lhs.val() == rhs.val();
}
friend constexpr bool operator != (MLL lhs, MLL rhs){
return lhs.val() != rhs.val();
}
};
const ll mod = 1e9 + 7;
using Z = MLL<mod>;
bool f(int x){
if(x < 10) return true;
std::string s = std::to_string(x);
int len = s.size();
fore(i, 0, len / 2)
if(s[i] != s[len - 1 - i])
return false;
return true;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::vector<int> PN;
PN.push_back(0);
fore(i, 1, 40001)
if(f(i))
PN.push_back(i);
std::vector<std::vector<Z>> dp(40005, std::vector<Z>(505, 0));
fore(j, 1, 500) dp[0][j] = 1;
fore(i, 1, 40001)
fore(j, 1, 500)
if(PN[j] <= i) dp[i][j] = dp[i][j - 1] + dp[i - PN[j]][j];
else dp[i][j] = dp[i][j - 1];
int t;
std::cin >> t;
while(t--){
int n;
std::cin >> n;
std::cout << dp[n][498] << endl;
}
return 0;
}