好久不更博了~~~

<h2>题目大意</h2>

定义一个数是好的当且仅当这个数 $x$ 满足 $l \leq x \leq r$

定义一个长度为 $n$ 的字符串的价值是所有好的数在这个字符串的出现次数的和。

现在给你 $l,r,n$ 让你构造出满足价值最大的情况下字典序最小的串。

$1 \leq l \leq r \leq 10^{800},1 \leq n \leq 2000$

<h2>题解</h2>

3500的题一看我就做不来。。
首先我们考虑如果 $r-l$ 比较小怎么办。
一个很显然的想法是将所有的数字暴力建 AC 自动机，然后 dp。
设 $f[i][j]$ 表示填了前 i 位，当前状态为 $j$ 的方案数。预处理 $g_i$ 表示 $i$ 状态能对答案造成的贡献。
求 $g_i$ 只需要把 fail 树建出来，然后求每个点到根的 $g$ 的和就可以了。
然后 $f[i][j] * g[ch] \to f[i+1][ch]$ 转移一下就好了。
现在考虑这个极其繁琐的限制 $l \leq x \leq r$。
想一想，我们如果暴力建出来 trie 树，这个树的形态会是一堆满 $10$ 叉子树，我们可以考虑压缩掉这些满 $10$ 叉子树。我们类比数位 dp 中卡上下界的方法，只需要把刚好“脱离”上下界的那些串建出来就好了。
于是我们现在设 $g[i][j]$ 表示第 $i$ 个点（按照未压缩树结构）继续走 $j$ 步对答案的贡献。然后更新一下就好了，最后转移是 $f[i][j] * \sum_{k=0}^{n-i-1}g[ch][k]\to f[i+1][ch]$
然后只需要前缀和优化一下就能快速转移了。

<h2>代码</h2>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 30000 + 5;
const int MAXM = 2000 + 5;

int chMAXN,fail[MAXN];
int gMAXN;
int tot = 1,rt = 1;
int n;
char L[MAXN],R[MAXN];
std::vector<int> G[MAXN];

inline int get(int x,int y){
    if(!chx) chx = ++tot;
    return chx;
}

inline void build(){
    int lenL = strlen(L+1),lenR = strlen(R+1);
    int u = 1,v = 1;
    if(lenL == lenR){
        FOR(i,1,lenL){
            if(u == v){
                FOR(k,L[i]-'0'+1,R[i]-'0'-1) gget(u,k)++;
                u = get(u,L[i]-'0');
                v = get(v,R[i]-'0');
            }
            else{
                FOR(k,L[i]-'0'+1,9) gget(u,k)++;
                u = get(u,L[i]-'0');
                FOR(k,i==1,R[i]-'0'-1) gget(v,k)++;
                v = get(v,R[i]-'0');
            }
        }
        gu++;if(u != v) gv++;
    }
    else{
        FOR(i,1,lenL){
            FOR(k,L[i]-'0'+1,9) gget(u,k)++;
            u = get(u,L[i]-'0');
        }
        FOR(i,1,lenR){
            FOR(k,i==1,R[i]-'0'-1) gget(v,k)++;
            v = get(v,R[i]-'0');
        }
        FOR(i,lenL+1,lenR-1) FOR(j,1,9) gget(rt,j)++;
        gu++;gv++;
    }
    // ~~~
    std::queue<int> q;
    FOR(i,0,9){
        if(chrt) failch[rt] = rt,q.push(chrt);
        else chrt = rt;
    }
    while(!q.empty()){
        int v = q.front();q.pop();
        FOR(i,0,n) gv += g[fail[v]][i];
        FOR(i,0,9){
            if(chv){
                failch[v] = ch[fail[v]][i],q.push(chv);
            }
            else chv = ch[fail[v]][i];
        }
    }
    FOR(i,1,tot) FOR(j,1,n) gi += gi;
    FOR(i,1,tot) FOR(j,0,9) Gch[i].pb(i);
}

int fMAXM,ans;
bool useMAXM;
// 第 i 位在第 j 个点上

inline void bfs(){
    std::queue<P> q;
    FOR(i,1,tot) if(fn == ans) q.push(MP(n,i)),usen = 1;
    while(!q.empty()){
        P v = q.front();q.pop();
        if(!v.fi) continue;
        for(auto x:G[v.se]){
            if(fv.fi-1+gv.se == fv.fi && !usev.fi-1){
                q.push(MP(v.fi-1,x));usev.fi-1 = 1;
            }
        }
    }
}

int main(){
    scanf("%s%s%d",L+1,R+1,&n);
    build();
    FOR(i,0,n) FOR(v,1,tot) fi = -1e9;
    f0 = 0;
    FOR(i,0,n-1){
        FOR(v,1,tot){
            if(fi < 0) continue;
            FOR(k,0,9){
                if(!chv) continue;
                fi+1[k]] = std::max(fi+1[k]],fi+gch[v][n-i-1]);
            }
        }
    }
    ans = -1e9;
    FOR(v,1,tot) ans = std::max(ans,fn);
    printf("%dn",ans);
    bfs();
    int now = 1;
    FOR(i,0,n-1){
        FOR(j,0,9){
            if(usei+1[j]] && fi+1[j]] == fi+gch[now][n-i-1]){
                printf("%d",j);
                now = chnow;break;
            }
        }
    }
    puts("");
    return 0;
}

<h2>总结</h2>

1. trie 树满叉结构是可以优化掉的。
2. 一般的这种 dp 还可以考虑加入每个点的贡献，每个结束点都会对 fail 树的子树有贡献。
3. 我太菜了，活该 pupil