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