广州小型网站建设公司,旅游景点网站建设毕业设计说明,建站模板招募设计师,河南网站建设多少钱C. Palindrome Basis 题意
定义一个正整数 a a a 是回文的#xff08;没有前导 0 0 0#xff09;当且仅当#xff1a; a a a 的十进制表示形式回文
给定一个正整数 n n n #xff0c;求出将 n n n 拆分成若干个回文数之和的方案数
思路
这是一个经典模型#xff0…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
#includebits/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 INF0x3f3f3f3f;
const long long INFLL1e18;typedef long long ll;templateclass T
constexpr T power(T a, ll b){T res 1;while(b){if(b1) 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;
}templatell 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_castll(OBJ)}constexpr MLL operator -() const{ //负号等价于加上ModMLL 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 MLLmod;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::vectorint PN;PN.push_back(0);fore(i, 1, 40001)if(f(i))PN.push_back(i);std::vectorstd::vectorZ dp(40005, std::vectorZ(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;
}
