题意：求\(\rm border\)长度为\(0\)的\(n\)位\(0,1\)字符串个数，并求字典序第\(k\)小的那一个。

首先是计数，正向不是很好算，考虑正难则反；设\(f_i\)表示长度为\(i\)的\(\rm |border|=0\)的串的个数

一个串可能有多个\(\rm border\)，我们考虑在其最小的\(\rm border\)长度\(j\)时计算它

则有\(f_i=2^i-\sum_{j=1}^{\lfloor \frac{i}{2}\rfloor}f_j2^{i-2\times j}\)；不用考虑长度大于\(\lfloor \frac{i}{2}\rfloor\)的\(\rm border\)是因为当\(\rm border\)长度大于\(\lfloor \frac{i}{2}\rfloor\)的时候一定存在一个小于\(\lfloor \frac{i}{2}\rfloor\)的\(\rm border\)。

第二问，考虑大力二分；二分一个串，，求所有字典序小于等于这个串中，\(\rm border=0\)的有多少个

设\(g_{0,i}\)表示长度为\(i\)且字典序严格小于当前串的前\(i\)位的串的个数；\(g_{1,i}\)表示长度为\(i\)且等于当前串的前\(i\)位的串的个数；不难发现\(g_{1,i}=[i\notin \rm Border]\)

还是跑上面那个容斥，从\(g_{1,j}\)向\(g_{0,i}\)转移的时候要在套一个二分判断一下

代码，其中有一些诡异的行为都是为了防爆unsigned long long

#include<bits/stdc++.h> #define re register #define LL unsigned long long int n,T;LL m,f[66],v[66]; LL g[2][66];int nxt[66],a[66]; inline void split(LL nw) { for(re int i=1;i<=n;i++) a[i]=nw>>(n-i)&1; } inline LL Calc(LL val,LL R,int i,int j,LL H) { LL L=0,k=0; while(L<=R) { LL mid=(L>>1ull)+(R>>1ull); if((L&1ull)&&(R&1ull)) mid++; LL t=(((val<<i)|mid)<<j)|val; if(t<H) k=mid+1,L=mid+1;else {if(mid) R=mid-1;else break;} } return k; } inline LL calc(LL nw) { split(nw);nxt[1]=0; for(re int i=2;i<=n;i++) { int p=nxt[i-1]; while(a[p+1]!=a[i]&&p) p=nxt[p]; if(a[p+1]==a[i]) nxt[i]=p+1;else nxt[i]=0; } memset(g,0,sizeof(g)); LL x=a[1];g[1][1]=1; if(x) g[0][1]=1;v[1]=x; for(re int i=2;i<=n;i++) { x=(x<<1ull)|a[i];v[i]=x; g[0][i]=x; for(re int j=1;j+j<=i;++j) { g[0][i]-=g[0][j]*(1ull<<(i-j-j)); if(g[1][j]) g[0][i]-=Calc(v[j],(1ull<<(i-j-j))-1,i-j-j,j,x); } if(!nxt[i]) g[1][i]=1; } return g[0][n]+g[1][n]; } int main() { scanf("%d",&T);f[1]=2; while(T--) { std::cin>>n>>m; for(re int i=2;i<=n;i++) { f[i]=1ull<<(i-1);f[i]--;f[i]+=1ull<<(i-1); for(re int j=1;2*j<=i;++j) f[i]-=(1ull<<(i-2*j))*f[j]; f[i]++; } std::cout<<f[n]<<std::endl; LL l=0,r=(1ull<<(n-1)),ans=0;r+=r-1; while(l<=r) { LL mid=(l>>1ull)+(r>>1ull); if((l&1ull)&&(r&1ull)) mid++; if(calc(mid)>=m) {ans=mid;if(mid) r=mid-1;else break;} else l=mid+1; } split(ans); for(re int i=1;i<=n;i++)putchar(a[i]+'a');puts(""); } }

[JSOI2016]无界单词