洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解
洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解
题目链接:B3883 [信息与未来 2015] 求回文数(加强版)
本题弱化版:B3882 [信息与未来 2015] 求回文数 ,把取模去掉就 OK 了。
题目描述:
一个正整数,正读和反读都相同的数为回文数,例如 \(22,131,2442,37073,6,\cdots\)。
所有的 \(1\) 位数都是回文数。
现给出一个正整数 \(n~(1\le n\le 10^{100})\),求出 \([1,n]\) 中的回文数的个数。
输入格式:
一个整数 \(n\)。
输出格式:
一个整数,即 \(1\sim n\) 中全部回文数的个数,答案对 \(20091119\) 取模。
伪装成简单数位dp的数位dp题,本题的回文串和 P3413 的回文子串是不一样的。
具体地说,我们无法在数位dp的转移过程中快速判断这个串是否仍然是回文串,状态也不好记。
不过由于本题条件十分简单,所以不由得让人好奇是否存在数学结论,尽管本题不像是纯数学题。
记 \(n\) 的十进制位数为 \(w\) 。注意到,当我们填出来的数有至少一位前导零时,即填出位数小于 \(w\) 的数时,
答案就等于:“存在多少个长度小于 \(w\) 的数字回文串”。通过组合计数可以得出答案为 \[ \begin{aligned} \mathrm{Ans}(w-1) =\sum_{i=1}^{w - 1} 9\times 10^{i - \left\lfloor\frac{i}{2}\right\rfloor - 1} = \sum_{i=1}^{w - 1} 9\times 10^{\left\lceil\frac{i}{2}\right\rceil - 1} \end{aligned} \] 其中 \(9\) 表示最高那一位不能填 \(0\) 。这个式子预处理一下 \(10\) 的幂,显然就可以随便 \(O(w)\) 计算出。
那么问题就转化为了,计算位数等于 \(w\) 且小于等于 \(n\) 的回文数的数量。
考虑数位dp。最简单的想法就是直接在数位dp的记忆化搜索过程中记录当前填了什么数,填好就暴力检验。
记 \(f(u,L)\) 为填到第 \(u\) 位(\(u=1\) 表示 \(n\) 的个位)时、是否存在高位限制 \((L=0 / 1)\) 的答案。
显然有个边界 \(f(\left\lfloor\frac{u}{2}\right\rfloor, 0) = 1\) ,因为如果填完 \(w\) 到 \(w - \left\lceil\frac{w}{2}\right\rceil + 1\) 且没有高位限制,那么剩下的怎么填都可以。
对于边界 \(f(\left\lfloor\frac{u}{2}\right\rfloor, 1)\) ,考虑直接暴力 \(O(w)\) 检验是否合法。于是乍一看,似乎复杂度是 \(O(w^2)\) 的……吗?
仔细想一想就会发现,记忆化搜索的过程中总共只会暴力检验一次 \(f(\left\lfloor\frac{u}{2}\right\rfloor, 1)\) 而已。
那么我们就不用记录填了什么数了,只需要特判一下这个边界情况就可以了,或者只有高位限制时记录即可。
答案就是 \((f(w,1) + \mathrm{Ans}(w-1)) \bmod p\) ,\(p\) 表示出题人给的模数。
时间复杂度 \(O(C\cdot w)\) ,其中常数 \(C\) 不超过 \(20\) 。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 20091119;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
template<typename T> void add(T &x, T y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(105))
int tot, now, num[N], tmp[N], pw10[N], f[N][2];
bool check()
{
for(int i = now, j = (tot + 1) / 2; i > 0 && j > 0; i--, j--)
{
if(tmp[i] > num[j]) return 0;
if(tmp[i] < num[j]) return 1;
}
return 1;
}
int dfs(int u, bool limit)
{
if(u == tot / 2)
{
if(limit == 0) return 1;
return check();
}
if(f[u][limit] != -1) return f[u][limit];
int res = 0, up = limit ? num[u] : 9;
rep(i, 0, up)
{
if(u == tot && i == 0) continue;
if(limit) tmp[++now] = i;
add(res, dfs(u - 1, limit && (i == up)));
if(limit) --now;
}
return f[u][limit] = res;
}
void pre()
{
pw10[0] = 1;
rep(i, 1, N - 3) pw10[i] = pw10[i - 1] * 10 % mod;
}
int solve(string str)
{
tot = str.size();
rep(i, 1, tot) num[i] = str[tot - i] - '0'; // 321 -> 1 2 3
int res = 0;
rep(i, 1, tot - 1) add(res, 9 * pw10[(i + 1) / 2 - 1] % mod);
memset(f, -1, sizeof(f));
add(res, dfs(tot, 1));
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
pre(); string n; cin >> n;
cout << solve(n) << '\n';
return 0;
}
参考文献:

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p216.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p233.webp)

