题目大意

戳我看题

字符集大小为 $m$，要求你构造一个最短的字符串，使得长度为 $n$的不同子串至少有 $K$个。

题目分析

原来我不会欧拉路.avi

思路很简单，首先，将任意长度为 $n-1$的子串看做节点，每个节点连 $m$条边出去到新的节点。可以证明（但没必要），原图存在一条欧拉回路。于是我们可以让字符串的任意长度为 $n$的子串都不相同，构造出的字符串长度就为 $n+K-1$。

但是图会非常大，我们不可能真的把这条欧拉回路找出来。

首先显然，如果我当前 dfs 的深度大于等于 $K$，那么已经出现了一条在图中走 $K$条边的路径，可以直接将该路径作为答案输出。

如果求欧拉路算法中的答案栈里面的边也有 $K$条了，也可以将他们作为答案输出了。

愚蠢的 litble 纠结了一上午为什么答案栈里面直接输出就行了，这充分说明了 litble 压根就不会欧拉路。因为 dfs 的过程是，若有能继续走的边，则一定继续走而不会返回，那么若将原图所有不再答案栈里面的边删除，每个点的出度也一定等于入度，答案边也一定构成了欧拉回路。所以这是没有问题的！

然后就是判断边有没有走过的问题了，虽然可以哈希，但效率更高的做法是，若原图中有 $2^{40}$以上的边，随机走走出合法路径的概率极大，所以就直接走。否则，用一个 long long 就可以完成哈希了。

由于我 dfs 的每一步操作，要么新走一个点让深度+1，要么回溯一下，深度-1 但答案栈里面的元素+1，所以复杂度是 $O(k)$的。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
const LL lim=1099511627776LL;
int n,m,K,top1,top2,dig[12],st1[200005],st2[200005];LL orzxzy;
map<LL,int> mp;

void print0() {for(RI i=1;i<=K+n-1;++i) printf("%d",dig[rand()%m]);}
void print1() {
    for(RI i=1;i<=n-1;++i) printf("%d",dig[0]);
    for(RI i=1;i<=K;++i) printf("%d",dig[st1[i]]);
}
void print2() {
    for(RI i=1;i<=n-1;++i) printf("%d",dig[0]);
    for(RI i=top2;i>=top2-K+1;--i) printf("%d",dig[st2[i]]);
}
void dfs(LL x) {
    if(top1>=K) {print1();exit(0);}
    for(RI i=0;i<m;++i) {
        LL kl=x*(LL)m+(LL)i;
        if(!mp[kl]) {
            mp[kl]=1,st1[++top1]=i;
            dfs(kl%orzxzy),--top1,st2[++top2]=i;
            if(top2>=K) {print2();exit(0);}
        }
    }
}
int main()
{
    srand(19260817);
    scanf("%d%d%d",&n,&m,&K);
    for(RI i=0;i<m;++i) scanf("%d",&dig[i]);
    LL orzabs=1;
    for(RI i=1;i<=n;++i) {
        orzabs*=(LL)m;
        if(orzabs>=lim) {print0();return 0;}
    }
    orzxzy=1;for(RI i=1;i<=n-1;++i) orzxzy*=(LL)m;
    dfs(0);
    return 0;
}