[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
    
     #include
     
      #include
      
       #include
       
        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) {            puts("0");            continue;        }        const int all=(1<
         
          >=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<