对每一位依次确定，问题即求长度不超过$n$且以$t$为前缀的合法串数
考虑其中一个串$s$，由于$s$以$t$为前缀，对于$s$的任意子串$s'$，显然均有$t
称满足上述性质的非循环串为半合法串，考虑一个出现了$cnt$次$t$的半合法串，将其旋转到所有以$t$为开头的位置，注意到这$cnt$个串中恰存在一个合法串，进而不妨看作每一个半合法串对答案的贡献为$\frac{1}{cnt}$
（注意出现次数包括首尾拼接，即需要再补上一个$t$除最后一个字符外的前缀）
忽略非循环串的限制，半合法串数可以使用下述dp计算——
对$t$建立KMP自动机（即$trans_{i,c}$为$t$最长的前缀满足其是$t[1,i]+c$的后缀），并定义$G_{len,node,cnt}$表示当前长度为$len,$位于节点$node,$且已经出现了$cnt$次$t$的（允许循环的）半合法串数，转移即$\begin{cases}G_{|t|,ed,1}=1\\G_{len,node,cnt}\rightarrow G_{len+1,trans(node,c),cnt+[trans(node,c)=ed]}\end{cases}$
（其中$st,ed$表示自动机的初始和结束状态$,c$要求不小于$t$中$node$对应位置的下一个字符）
关于首尾拼接，记$P_{node}$表示在$node$的基础上加入$t$除最后一个字符外的前缀后经过$ed$的次数，最终将$G_{len,node,cnt}\rightarrow F'_{len,cnt+P_{node}}$即得到忽略非循环串限制的答案
进一步的，对循环串枚举循环次数$k$和循环节长度$d$和循环次数$k$，转移即
$$
F_{len,cnt}=F'_{len,cnt}-\sum_{k\ge 2,k\mid \gcd(len,cnt),d=\frac{len}{k}}\begin{cases}F_{d,\frac{cnt}{k}}&d\ge |t|\\ [t[1,d]是合法串且t在(t[1,d])^{k}中出现了cnt次] &d<|t|\end{cases}
$$
单次dp复杂度为$o(n^{3}|\Sigma|)$，需要做$o(n|\Sigma|)$次dp，总复杂度为$o(n^{4}|\Sigma|^{2})$，可以通过
另外，关于答案存储，注意到循环串数量仅有$o(|\Sigma|^{\frac{n}{2}})$，因此计数中将答案对$10^{36}$取$\min$即可（用__int128存储）
1 #include
2 using namespace std;
3 #define N 55
4 #define D 26
5 #define ll long long
6 #define LL __int128
7 int n,m,l,nex[N],vis[N],P[N];
8 ll K0;
9 LL V=1e36,K,g[N][N][N],f[N][N];
10 char s[N];
11 void Add(LL &x,LL y){
12 x=min(x+y,V);
13 }
14 bool check(){
15 for(int i=1;i<=m;i++){
16 bool flag=0;
17 for(int j=1;j<=m;j++){
18 if (s[(i+j-2)%m+1]1;
19 if (s[(i+j-2)%m+1]!=s[j])break;
20 }
21 if (flag)return 0;
22 }
23 for(int i=1;i)
24 if (m%i==0){
25 bool flag=0;
26 for(int j=1;j<=m-i;j++)
27 if (s[j]!=s[j+i]){
28 flag=1;
29 break;
30 }
31 if (!flag)return 0;
32 }
33 return 1;
34 }
35 void init(){
36 nex[0]=nex[1]=0;
37 for(int i=2,j=0;i<=m;i++){
38 while ((j)&&(s[j+1]!=s[i]))j=nex[j];
39 if (s[j+1]==s[i])j++;
40 nex[i]=j;
41 }
42 int m0=m;
43 memset(vis,0,sizeof(vis));
44 for(int i=1;i<=m0;i++){
45 m=i,vis[i]=check();
46 if (!vis[i])continue;
47 for(int j=1;j<=m0-i;j++)
48 if (s[j]!=s[j+i]){
49 vis[i]=0;
50 break;
51 }
52 }
53 memset(P,0,sizeof(P));
54 for(int node=0;node<=m;node++){
55 int k=node;
56 for(int j=1;j){
57 char c=s[k+1];
58 if (k==m)c=s[nex[k]+1];
59 if (s[j]<c){
60 P[node]=-1;
61 break;
62 }
63 while ((k==m)||(k)&&(s[k+1]!=s[j]))k=nex[k];
64 if (s[k+1]==s[j])k++;
65 if (k==m)P[node]++;
66 }
67 }
68 }
69 LL calc(){
70 init();
71 for(int i=1;i)
72 if (s[nex[i]+1]>s[i+1])return 0;
73 memset(g,0,sizeof(g));
74 g[m][m][1]=1;
75 for(int len=m;len)
76 for(int node=m;node>=0;node--)
77 for(int cnt=1;cnt<=len-m+1;cnt++){
78 if (!g[len][node][cnt])continue;
79 int d=s[node+1]-'a';
80 if (node==m)d=s[nex[node]+1]-'a';
81 for(int c=d;c){
82 int k=node;
83 while ((k==m)||(k)&&(s[k+1]!=c+'a'))k=nex[k];
84 if (s[k+1]==c+'a')k++;
85 Add(g[len+1][k][cnt+(k==m)],g[len][node][cnt]);
86 }
87 }
88 memset(f,0,sizeof(f));
89 for(int len=m;len<=n;len++)
90 for(int node=0;node<=m;node++)
91 for(int cnt=1;cnt<=len-m+1;cnt++)
92 if (P[node]>=0)Add(f[len][cnt+P[node]],g[len][node][cnt]);
93 LL ans=0;
94 for(int len=m;len<=n;len++)
95 for(int cnt=1;cnt<=n;cnt++){
96 for(int k=2;k<=min(len,cnt);k++)
97 if ((len%k==0)&&(cnt%k==0)){
98 int d=len/k;
99 if (d>=m)f[len][cnt]-=f[d][cnt/k];
100 else{
101 if ((vis[d])&&(k==cnt))f[len][cnt]--;
102 }
103 }
104 Add(ans,f[len][cnt]/cnt);
105 }
106 return ans;
107 }
108 void write(LL x){
109 if (!x)return;
110 write(x/10);
111 putchar(x%10+'0');
112 }
113 int main(){
114 scanf("%d%lld%s",&n,&K0,s+1);
115 l=strlen(s+1),K=K0-1;
116 for(m=1;m<=l;m++){
117 int d=s[m]-'a';
118 for(int c=0;c'a',K+=calc();
119 s[m]=d+'a';
120 if (check())K++;
121 }
122 for(m=1;m<=n;m++){
123 for(int c=0;c){
124 s[m]=c+'a';
125 LL cnt=calc();
126 if (K<=cnt)break;
127 K-=cnt;
128 if (c==D-1){
129 printf("-1\n");
130 return 0;
131 }
132 }
133 if ((check())&&(--K==0))break;
134 }
135 for(int i=1;i<=m;i++)putchar(s[i]);
136 putchar('\n');
137 return 0;
138 }