[CC-BSTRLCP]Count Binary Strings

题目大意：

对于一个长度为\(n\)的\(\texttt0/\texttt1\)串\(S\)，如果存在一个切分\(i\)，使得\(S_{[1,i]}\)与\(S_{[i+1,n]}\)的LCP长度\(>k\)，那么称\(i\)是\(S\)的精准切分。

如果\(S\)至少有\(m\)个精准切分，那么称\(S\)是一个切分串。

给定\(n,k,m\)，求有多少长度为\(n\)的切分串。

• \(1\le T\le 5\)
• \(1\le n\le50\)
• \(0\le m\le n-1\)
• \(0\le k\le \min(10,n)\)

思路：

枚举前\(k\)位的状态\(s\)，\(f[i][j][k]\)表示考虑到第\(i\)位，已经有\(j\)个精准切分，最后匹配的长度为\(k\)的方案数。

预处理每种后缀能匹配\(s\)的多长的前缀，转移时枚举最后加上\(0\)还是\(1\)即可。

时间复杂度\(\mathcal O(4^kk+2^kn^2k)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int N=51,K=11,M=1024,mod=1e9+7;

int f[2][N][K],g[M][K];

inline void upd(int &a,const int &b) {

	(a+=b)%=mod;

}

int main() {

	for(register int T=getint();T;T--) {

		const int n=getint(),k=getint(),m=getint();

		if(k==0) {

			printf("%lld\n",(1ll<<n)%mod);

			continue;

		}

		if(m+1==n||k*2>n) {

			puts("0");

			continue;

		}

		const int all=(1<<k)-1;

		int ans=0;

		for(register int s=0;s<=all/2;s++) {

			int p[k+1];

			for(register int i=0,t=s;i<=k;i++) {

				p[k-i]=t;

				t>>=1;

			}

			memset(f[0],0,sizeof f[0]);

			for(register int t=0;t<=all;t++) {

				for(register int i=1;i<=k;i++) {

					int l;

					for(l=i;l;l--) {

						if(p[l]==(t&((1<<l)-1))) break;

					}

					g[t][i]=l;

				}

				f[0][t==s][g[t][k]]++;

			}

			for(register int i=k*2+1;i<=n;i++) {

				const bool cur=i&1;

				memset(f[cur],0,sizeof f[cur]);

				for(register int j=0;j<=i;j++) {

					for(register int i=0;i<=k;i++) {

						for(register int b=0;b<2;b++) {

							const int t=((p[i]<<1)|b)&all;

							const int l=g[t][std::min(i+1,k)];

							upd(f[cur][j+(l==k)][l],f[!cur][j][i]);

						}

					}

				}

			}

			for(register int j=m+1;j<=n;j++) {

				for(register int i=0;i<=k;i++) {

					(ans+=f[n&1][j][i])%=mod;

				}

			}

		}

		printf("%d\n",(ans<<1)%mod);

	}

	return 0;

}