Luogu

分析

容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。

第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到

$$dp_i=2^i-\sum_{j=1}^{i/2}dp_j\times 2^{i-2j}$$

第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$，如果 $s<k$ 则将当前字符设为 b 并将 $k$ 减去 $s$。

那么我们需要计算确定了前 $len$ 个字符情况下无界单词的个数，仍然考虑 DP。

设 $dp_i$ 表示确定了前 $len$ 位长度为 $i$ 的无界单词的个数，转移时分类讨论

• 若 $i\leq len$，则需要判断前 $i$ 位是否存在 border，KMP 预处理出 $nxt$ 即可。
• 否则，转移方程为 $\displaystyle dp_i=2^{i-len}-\sum_{j=1}^{i/2}w_j$，其中的 $w_j$ 的值需要分类讨论
  • 若 $j\geq len$，则 $w_j=dp_j\times 2^{i-2j}$。
  • 若 $j<len$ 且 $i-j\geq len$，则 $w_j=dp_j\times 2^{i-j-len}$。
  • 若 $j<len$ 且 $i-j<len$，则需要判断 $s_{1..len-i+j}$ 是否为 $s_{1..len}$ 的一个 border 和 $dp_j$ 是否为 $1$，如果都满足则 $w_j=1$，否则 $w_j=0$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef unsigned long long ull;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=64+10;

int n; ull k,pw[N];
int s[N],nxt[N];
ull dp[N];

inline void getnext(int len) {
    for (re int i=2,j=0;i<=len;++i) {
        while (j&&s[j+1]!=s[i]) j=nxt[j];
        if (s[j+1]==s[i]) ++j;
        nxt[i]=j;
    }
}

inline ull calc(int len) {
    memset(dp,0,sizeof(dp));
    for (re int i=1;i<=n;++i) {
        if (i<=len) dp[i]=!nxt[i];
        else { dp[i]=pw[i-len];
            for (re int j=1;j<=i/2;++j) {
                if (j>=len) dp[i]-=dp[j]*pw[i-(j<<1)];
                else if (len<=i-j) dp[i]-=dp[j]*pw[i-len-j];
                else if (dp[j]) { int flag=1;
                    for (re int p=1,q=i-j+1;q<=len;++p,++q)
                        if (s[p]!=s[q]) { flag=0; break; }
                    if (flag) --dp[i];
                }
            }
        }
    }
    return dp[n];
}

int main() {
    pw[0]=1; for (re int i=1;i<64;++i) pw[i]=pw[i-1]<<1;
    int T=read();
    while (T--) {
        n=read(),scanf("%llu",&k);
        printf("%llu\n",calc(0));
        for (re int i=1;i<=n;++i) {
            s[i]=0,getnext(i);
            ull r=calc(i);
            if (k>r) k-=r,s[i]=1;
        }
        for (re int i=1;i<=n;++i) putchar(s[i]+'a'); puts("");
    }
    return 0;