我们抬头仰望同一片星空，在万家灯火熄灭的时候……
本来打算先改考试题在finish，结果鹤了一下午+半个晚上也没鹤对，鹤的T2还被卡了却依然不知道为什么那个贪心是假的……
香山的树
——以下内容来自：鹤的
又学了一个新词汇：lyndon串，一个字符串是lyndon串当且仅当它的最小循环表示是它本身，且它不是循环串。
求长度不超过 n 且字典序大于等于 p 的所有 lyndon 串中，字典序第 k 小的那个。
每次算出以p(是变化的)开头的 lyndon 串个数x。
如果x >= k说明p一定是答案的前缀，如果p不是答案，就给k减1并在p后面填一个a继续做。
如果x < k，说明x小了一定不是答案的前缀，把k – x，如果p末尾有z的话先删掉，然后让p的最后一位变大1继续做。
对于一个合法串，若p在其中出现了c次，那么它有c种循环表示的开头是p，设 s 为某个合法串开头为p的某个循环表示，每个s只会对应一个合法串，就是它的最小循环表示，可以让每个s都给答案1/c的贡献，最终每个合法串都会被恰好算一次。
s的条件：开头为p；s中任意长度为m的子串都不小于p；s不是循环串。
——-以上内容来自：鹤的
先不管s不是循环串的条件，初始答案要算出来所有s是循环串的情况，那么循环节长度为n就是我们要求的答案在乘1/c贡献之前的值。既然s是循环串，它的起点就不再重要，为了方便记录答案，可以找一个起点确定并且终点也确定的位置作为起点，一个很好的选择是从sm+1开始。
设dpi,j,c为从sm+1开始走i步，和 p 正在尝试匹配第 j 个字符(由于s是一个由我们构造出来的串，所以用它转移/统计答案时表示成功地匹配完了 j ，因为它已经统计上了所有的来路，它自己算一种*1)，共匹配了 c 次 p 的方案数。长度为 i 时走了 i-1 步，重复出现k次时下标是k-1，因为次数是在开始时累加的，而初值从0开始转移。因为sm+1是起点，所以要强制在最后一步匹配到了p，为了保证合法，每次失配时强制s那位比p那位大。
用g[i]记录用以上算法算出的长度为 i的答案，f[i]表示实际的答案。
由于最终计算f[i]的式子g[i]和f[i]都乘了一个下标，所以在累计g的时候把长度乘上，不要忘了乘1/c，在计算的时候比较大的g[i]表示i*g[i]，比较小的由于已经被减完了所以是i*f[i]，最终的答案是 f 的和，把下标去掉。
目前认为在判断s这个开头是不是答案是只需要判断K是不是等于1，还有算g[i]的时候gcd(i,k)其实就是k，打算去尝试一下再回来upd。(如果你知道也可以回复thank you)
code 是鹤的
#include <bits/stdc++.h>
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] < s[j]) return 0;
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<n; i++) for(int j=1; j<=m; j++) for(int k=0; k<=i; k++)
{
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;
}
原文地址：http://www.cnblogs.com/Catherine2006/p/16882643.html
