洛谷P3413 SAC#1 - 萌数题解

题目链接：P3413 SAC#1 - 萌数

题意：

定义存在长度至少为 \(2\) 的回文子串的数是萌的，比如 \(101,110\) 是萌的，\(102,1201\) 不是萌的。

计算区间 \([l,r]\) 的所有整数中有多少萌数，答案对 \(10^9+7\) 取模。

输入格式：

输入包含仅 \(1\) 行，包含两个整数：\(l, r\)。

输出格式：

输出仅 \(1\) 行，包含一个整数，即为答案。

数据范围：

保证 \(1 \le l < r \le 10^{1000}\) 。

考虑数位dp。注意到任意一段数字字符串，只要拼接上 \(\mathtt{AA}\) 或者 \(\mathtt{ABA}\) 就会变成萌萌的。

因此我们只需要在数位dp的转移过程中，记录当前位某一侧的两个数是什么就行了。

以及计算 \([l,r]\) 之间的答案，我们可以通过 \([0,r]\) 的结果减去 \([0,l-1]\) 的结果来得到答案。

问题转化为给出巨大整数 \(w\) 时，如何计算 \([0,w]\) 的答案。记 \(w\) 的位数为 \(n\) ，第 \(i\) 位为 \(w_i\) ，\(w_1\) 表示个位。

设 \(f(u,x,y,S,L,Q)\) 为考虑到 \(w\) 的第 \(u\) 位，\(u+1\) 为 \(x\) ，\(u+2\) 为 \(y\) ，是否已经是萌的了 \((S=0/1)\)，

是否存在高位限制 \((L=0/1)\) ，是否允许前导零 \((Q=0/1)\) 时的答案。边界有 \(f(0, x, y, S, L, Q)=S\) 。

其中 \(x,y\) 是填的数字，当 \(x=-1\) 或 \(y=-1\) 时表示不存在这一位。那么 \(w\) 的答案就是 \(f(n,-1,-1,0,1,1)\) 。

考虑转移，只需要枚举 \(u\) 这一位填什么数字即可，记这一位最多填到 \(m\)，那么 \[ \begin{aligned} f(u,x,y,S,L,Q) = &\sum_{i(i>0)}^{m} f(u-1,i,x,S\lor(i=x\lor i=y),L\land(i=m),0) \\[6pt]&+Q\cdot f(u-1,-1,-1,S,0,1) \end{aligned} \]

第二行表示填 \(0\) 的情况（前导零，实际上是留空的），仔细想一下就会发现是这样的。

考虑记忆化搜索。可以发现转移的时候，\(y\) 是不需要记忆化的（下一层用不到就不会重复调用了）。

时间复杂度 \(O(800\cdot n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
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)(1e3 + 15))

char L[N], R[N];
int num[N], f[N][12][2][2][2];
int dfs(int u, int x, int y, bool st, bool limit, bool qd0)
{
    if(u == 0) return st;
    if(x != -1 && y != -1 && f[u][x][st][limit][qd0] != -1) return f[u][x][st][limit][qd0];
    int res = 0, up = limit ? num[u] : 9;
    rep(i, 0, up)
    {
        if(qd0 && (i == 0)) { add(res, dfs(u - 1, -1, -1, st, 0, 1)); }
        else { add(res, dfs(u - 1, i, x, st || (i == x || i == y), limit && (i == up), 0)); }
    }
    if(x != -1 && y != -1) f[u][x][st][limit][qd0] = res;
    return res;
}
int solve(char *str, int tot, bool sub)
{
    memset(num, 0, sizeof(num));
    rep(i, 1, tot) num[tot - i + 1] = str[i] - '0'; // 321 -> 1 2 3
    if(sub)
    {
        int t = 1;
        while(t <= tot && num[t] == 0) { num[t] = 9, ++t; }
        if(t <= tot) num[t] -= 1;
        while(tot > 0 && num[tot] == 0) --tot;
        if(tot == 0) return 0;
    }
    memset(f, -1, sizeof(f));
    return dfs(tot, -1, -1, 0, 1, 1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (L + 1) >> (R + 1);
    int res = solve(R, strlen(R + 1), 0);
    add(res, mod - solve(L, strlen(L + 1), 1));
    cout << res << '\n';
    return 0;
}