题意：定义F[0]=0，F[1]=1，F[i]=F[i-1]+F[i-2](字符串拼接)。
题解：我们可以定义dp[i][l][r]表示当前轮能匹配到区间[l,r]的方案数。因此有如下转移
dp[i][l][r]+=dp[i-1][l][r]
dp[i][l][r]+=dp[i-2][l][r]
dp[i][l][r]+=dp[i-1][l][k]*dp[i-2][k+1][r]
之后我们考虑不需要匹配但是影响方案数的部分。
对于F(i-1)中已经匹配上结尾，dp[i][l][r](r==len)的情况，我们可以往后面添加F(i-2)长度的个数，也就是方案数*2^(len(F-2))。
对于F(i-2)中已经匹配上开头，dp[i][l][r](l==1)的情况，我们可以往前面添加F(i-1)长度的个数，也就是方案数*2^(len(F-1))。
AC代码：
#include<stdio.h> #define mod 1000000007 typedef long long ll; ll dp[105][105][105]; ll f[105]; char a[105]; int main() { ll len,n; scanf("%lld%lld%s",&len,&n,a+1); for(ll i=1;i<=len;i++)dp[a[i]-'0'][i][i]=1; f[0]=f[1]=2; for(ll i=2;i<=n;i++) f[i]=(f[i-1]*f[i-2])%mod; for(ll i=2;i<=n;i++) for(ll l=1;l<=len;l++) for(ll r=l;r<=len;r++) { dp[i][l][r]=(dp[i][l][r]+(r==len?f[i-2]:1)*dp[i-1][l][r]%mod+(l==1?f[i-1]:1)*dp[i-2][l][r]%mod)%mod; for(ll k=l;k<r;k++) dp[i][l][r]=(dp[i][l][r]+dp[i-1][l][k]*dp[i-2][k+1][r])%mod; } printf("%lld\n",dp[n][1][len]); }