浓浓的一股DP味。。。

但是猜不出来是什么DP。


原来这玩意是个容斥DP。

设$f_i$为长度为$i$的无界单词个数。

boader:边界;

不难发现,一个长度为$i$的单词的最小boader长度的最大值为$\lfloor\frac{i}{2}\rfloor$。

因为你可以发现,大于$\lfloor\frac{i}{2}\rfloor$这个长度的都存在一个小于或等于$\lfloor\frac{i}{2}\rfloor$的boader。

因此有

$f_i=2^i-\sum\limits_{j=1}^{\lfloor\frac{i}{2}\rfloor}f_j*2^{i-2j}$

这个就是方案数。

如果求要求具体方案的话,

就用试填法,一位一位填。

计算$[1,i]$已填的方案数,决定$i$位填什么。

具体流程可以照着代码来。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=505,mod=1e9+7;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ull f[N],g[N],K;char s[N];int nxt[N],n;
ull calc(int l)
{
    memset(g,0,sizeof(g));nxt[1]=0;
    for(int i=2,j=0;i<=l;i++)
    {
        while(j&&s[j+1]!=s[i])j=nxt[j];
        if(s[j+1]==s[i])++j;nxt[i]=j;
    }
    for(int i=1;i<=l;i++)
        if(!nxt[i])g[i]=1;
    for(int i=l+1;i<=n;i++)
    {
        g[i]=1ull<<(i-l);
        for(int j=1;j<=i/2;j++)
        {
            if(l+j<=i)g[i]-=g[j]*(1ull<<(i-j-max(j,l)));
            else if(g[j])
            {
                bool flag=1;
                for(int k=1;k<=l-(i-j);k++)
                    if(s[k]!=s[k+(i-j)]){flag=0;break;}
                g[i]-=flag;
            }
        }
    }
    return g[n];
}
int main()
{
    f[1]=2;
    for(int i=1;i<=64;i++)
    {
        if(i==64)f[i]=0;
        else f[i]=1ull<<i;
        for(int j=1;j<=i/2;j++)
            f[i]-=f[j]*(1ull<<(i-2*j));
    }
    int T;qr(T);
    while(T--)
    {
        qr(n),qr(K);
        qw(f[n]);puts("");
        for(int i=1;i<=n;i++)
        {
            s[i]='a';
            ull x=calc(i);
            if(K>x){s[i]='b';K-=x;}
        }
        for(int i=1;i<=n;i++)putchar(s[i]);
        puts("");
    }
    return 0;
}