没看懂啥意思。

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=110;
int dp[N],cnt[N],pre[N],g[N];
char s[N];
void solve()
{
	int n,m;cin>>n>>m;
	memset(cnt,0,sizeof(cnt));
	cout<<dp[n]<<'\n';
	s[n+1]=0,g[1]=1;s[1]='a';
	if(m>(dp[n]>>1))s[1]='b',m-=(dp[n]>>1);
	for(int i=2,pos;i<=n;i++)
	{
		s[i]='a',pos=0;
		for(int j=2;j<=i;j++)
		{
			while(pos&&s[pos+1]!=s[j])pos=pre[pos];
			if(s[pos+1]==s[j])pos++;
			pre[j]=pos,g[j]=!pos;
		}
		for(;pos;pos=pre[pos])cnt[pos]=i;
		for(int j=i+1;j<=n;j++)
		{
			g[j]=1ull<<(j-i);
			for(int k=1;k*2<=j;k++)
			{
				if(k>=i)g[j]-=g[k]*(1ull<<(j-k*2));
				else if(k<=j-i)g[j]-=g[k]*(1ull<<(j-i-k));
				else if(cnt[k+i-j]==i)g[j]-=g[k];
			}
		}
		if(g[n]<m)s[i]='b',m-=g[n];
	}
	printf("%s\n",s+1);
}
signed main()
{
	for(int i=1;i<=64;i++)
	{
		if(i!=64)dp[i]=(1ull<<i);
		for(int j=1;j*2<=i;j++)
			dp[i]-=dp[j]*(1ull<<(i-j*2));
	}
	int t;cin>>t;
	while(t--)solve();
	return 0;
}