洛谷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;
}

参考文献:

[1] https://www.luogu.com.cn/article/3fyzcjec