探索Lyndon串的奥秘

#include 
using namespace std;
typedef long long ll;
const int maxn = 53;
const int mod = 998244353;
const ll inf = 4e18;
int n, m, nxt[maxn];
ll f[maxn][maxn][maxn], g[maxn], K;
char s[maxn];
#define gcd __gcd
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch <'0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x <<1) + (x <<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
inline bool inc() {for( ; m&&s[m]=='z'; s[m--]=0); return m?s[m]++,1:0;}
inline void add(ll &x, ll y) {x = min(inf, x+y);}
inline ll mul(ll x, ll y) {return 1.0*x*y>2*inf?inf:min(inf, x*y);}
inline bool chk()
{
    for(int i=2; i<=m; i++)
    {
        if(strcmp(s+1, s+i)>0) return 0;
    }
    return 1;
}
inline bool chk2(int j=1)
{
    for(int i=2; i<=m; i++)
    {
        if(s[i]         if(s[i] == s[j]) j++;
        else j = 1;
    }
    return 1;
}
ll calc()
{
    if(!chk2()) return 0;
    for(int i=2,j=0; i<=m; i++)
    {
        while(j && s[j+1] != s[i]) j = nxt[j];
        if(s[j+1] == s[i]) j++;
        nxt[i] = j;
    }
    memset(f, 0, sizeof(f));
    f[0][nxt[m]+1][0] = 1;
    for(int i=0; i    {
        if(f[i][j][k])
        {
            add(f[i+1][j==m?nxt[m]+1:j+1][k+(j==m)], f[i][j][k]);
            add(f[i+1][1][k], mul(f[i][j][k], 'z'-s[j]));
        }
    }
    memset(g, 0, sizeof(g));
    for(int i=1; i<=n; i++) for(int k=1; k<=i; k++)
    {
        add(g[i], mul(f[i-1][m][k-1]/(k/gcd(i,k)), i/gcd(i,k)));
    }
    for(int i=1; i<=n; i++) for(int j=i+i; j<=n; j+=i) if(g[j] != inf) g[j] -= g[i];
    for(int i=m; i<=n; i++) if(g[i] == inf) return inf;
    ll x = 0; for(int i=m; i<=n; i++) add(x, g[i]/i);
    return x;
}
int main()
{
    scanf("%d%lld%s", &n, &K, s+1);
    m = strlen(s+1);
    while(1)
    {
        ll x = calc();
        if(K > x)
        {
            K -= x;
            if(!inc()) puts("-1"), exit(0);
        }
        else 
        {
            if(chk() && !--K) puts(s+1), exit(0);
            s[++m] = 'a';
        }
    }
    return 0;
}