CF1110H Modest Substrings 题解

题意：

给定两个正整数 \(l, r\) ，称整数 \(x\) 为好的，当且仅当 \(l \leq x \leq r\) 。

对一个由 \(\texttt{0-9}\) 中数字构成的字符串，定义它的权值为这样的非空子串个数：

它不以 \(\texttt{0}\) 开头，且将其看成数字后是好的。

你需要找到一个长度为 \(n\) 的字符串，使得它的权值最大。

如果有多个字符串, 你需要寻找字典序最小的一个。同时，字符串可以有前导零。

输入格式：

三行，每行一个正整数，第一行为 \(l\) ，第二行为 \(r\) ，第三行为 \(n\) 。

输出格式：

两行，第一行表示最大权值，第二行表示权值等于最大权值的最小大数。

数据范围：

\(1 \leq l,r \leq 10^{800} , 1 \leq n \leq 2000\) 。

复活后的第一道黑题，有一说一难度确实很高。

首先考虑 \(l,r\) 相差较小的情况，可以考虑对 \([l,r]\) 间的所有数字建 \(\mathtt{AC}\) 自动机，然后在上面跑 dp 统计答案。

考虑节点 \(i\) 代表的串对答案的贡献 \(g_i\) ，则 \(g_i\) 为节点 \(i\) 跳失配指针能到的点的贡献总和，即 \[ \begin{aligned} g_v \uparrow g_{\texttt{fail}_v} &&&&\big(a\uparrow b := a \gets a + b\big) \end{aligned} \] 设 \(f_{i,j}\) 表示在节点 \(j\) 上组成 \(i\) 位数的方案数，显然可以拿 \(f_{l,u} + g_v\) 来更新 \(f_{l+1,v}\) ，答案就是 \(\max f_{n,i}\)

但是这里 \(l,r\) 相差巨大，所以不能直接暴力建 \(\mathtt{AC}\) 自动机。

容易发现，暴力 \(\mathtt{AC}\) 自动机中有很多节点，以它为根的子树都是一个满十叉树，而这些树并不那么有用。

例如 \([1000,2333]\) 间，枚举到 \(11\_\,\_\) 时，后面怎么填都行，而我们朴素dp会把每个都跑一次。

显然我们会想到把这些节点缩起来。考虑将一个深度为 \(l\) 的满十叉树缩成一个点（有 \(10^{l}\) 个叶结点的满十叉树）

于是，当走到这个点的时候，再任意走 \(l\) 步（但是至少走 \(l\) 步才能产生贡献），就一定能产生一个匹配

也就是说我们对这个根节点打上一个长度为 \(l\) 的标记，表示只要再走 \(l\) 步就可以得到 \(1\) 的贡献

当然，一个点可能被打上多个标记。因此实际上，我们对一个点存储的信息是：长度为 \(l\) 的标记的数量。

这样就比刚才的更好更早多了，可以通过 \(\mathtt{dfs}\) 构造，思想类似于数位dp，详见代码。

对于 dp 的转移，只需要枚举下一个字符是 \(\mathtt{0 \sim 9}\) 中的哪一个，然后去 \(\mathtt{AC}\) 自动机上跑，

再根据当前串长 \(l\) 决定加入哪些标记。具体地，设串长为 \(l\) ，则长度小于 \(l\) 的标记都是有效的，考虑前缀和处理。

最后就是输出方案的问题，因为要求字典序最小，而传统的转移方向会求出翻转后字典序最小的串。

因此考虑换一个转移方向。用 \(f_{i,j}\) 表示总长度为 \(i\) 的串，初始时自动机在位置 \(j\) 所可以获得的最大权值。

这里的区别在于：一般是默认从 \(\mathtt{AC}\) 自动机的根出发，枚举最后到了哪里。

设自动机转移 \(j \to k\) ，则我们用 \(f_{i+1,k}\) 去更新 \(f_{i,j}\) ，这样就可以顺便记录选哪个字符更优，从而输出方案

时间复杂度 \(\mathcal{O}(n \log r \cdot \Sigma^2)\) ，其中 \(\Sigma=10\) 为字符集大小，\(r = 10^{800}\) 为值域。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))
#define M (N * 16)

int n,fail[N][M];
char L[N],R[N],fr[N][M],buf[N];
namespace AC
{
    queue<int> q; 
    char tmp[N]; int cnt = 1, limit;
    int fail[M], d[M][10], v[M][N], sum[M][N];
    void dfs(int x,int dep, bool bl = 1, bool br = 1)
    {
        if(!(bl || br) || dep == limit) { ++v[x][limit - dep]; return; }
        int m = br ? R[dep] : 9;
        for(int i = (bl ? L[dep] : 0); i <= m; i++)
            dfs(d[x][i] ? d[x][i] : (d[x][i] = ++cnt), dep + 1, bl && i == L[dep], br && i == R[dep]);
    }
    void init()
    {
        int nL = strlen(L), nR = strlen(R); char *p;
        for(p = L; *p; (*p++) &= 15); for(p = R; *p; (*p++) &= 15);
        if(nL == nR) return limit = nL, dfs(1,0);
        memcpy(tmp, R, nR); memset(R, 9, nL), limit = nL, dfs(1,0);
        memcpy(R, tmp, nR), memset(L, 0, nR), L[0] = 1, limit = nR, dfs(1,0);
        for(int i = nL + 1; i < nR; i++)
            for(int j = 1; j < 10; j++) ++v[ d[1][j] ? d[1][j] : (d[1][j] = ++cnt) ][i - 1];
    }
    void build()
    {
        
        for(q.push(1), fail[1] = 0; !q.empty(); q.pop())
            for(int i = q.front(), id = 0; id < 10; ++id)
            {
                int t = (fail[i] ? d[fail[i]][id] : 1), &u = d[i][id];
                if(!u)  { u = t; continue; } fail[u] = t; q.push(u);
                for(int j = 0; j < n; j++) v[u][j] += v[t][j];
            }
    }
    void psum() { for(int i = 1; i <= AC::cnt; i++) partial_sum(v[i], v[i] + n, sum[i]); }
}
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 >> R >> n; AC::init(); AC::build(); AC::psum();

    for(int i = 1,nj,nv; i <= n; i++)
        for(int j = 1; j <= AC::cnt; j++)
            for(int d = 0; d < 10; d++)
            {
                nj = AC::d[j][d], nv = fail[i - 1][nj] + AC::sum[nj][i - 1];
                if(nv > fail[i][j]) { fail[i][j] = nv, fr[i][j] = d; }
            }
    cout << fail[n][1] << '\n'; int t = 1; 
    for(int i = n; i; t = AC::d[t][fr[i][t]], --i) cout << (char)(fr[i][t] + '0');
    return 0;
}