class="markdown_views prism-github-gist">

题意

定义F(x)为F(x-1)与F(x-2)的连接（其中F(0) = ‘0’,F(1) = ‘1’）。
给出一个长度不超过100的字符串s，询问s在F(x)的所有子序列中出现了多少次。

---

题解

数量很大的计数问题，我们首先想到的解决方案就是dp。
我们考虑F(x) = F(x-1) + F(x-2)
是由两部分构成的，我们可以分治来计算。
s[1,n]在F(x)中出现的次数由几部分构成：

• s[1,n]" role="presentation" style="position: relative;">s[1,n]$s[1,n]$在F(x−1)" role="presentation" style="position: relative;">F(x−1)$F(x-1)$中出现的次数乘以2len(F(x−2))" role="presentation" style="position: relative;">2len(F(x−2))$2^{len(F(x-2))}$
• s[1,n]" role="presentation" style="position: relative;">s[1,n]$s[1,n]$在F(x−2)" role="presentation" style="position: relative;">F(x−2)$F(x-2)$中出现的次数乘以2len(F(x−1))" role="presentation" style="position: relative;">2len(F(x−1))$2^{len(F(x-1))}$
• s[1,k]" role="presentation" style="position: relative;">s[1,k]$s[1,k]$在F(x−1)" role="presentation" style="position: relative;">F(x−1)$F(x-1)$中出现的次数*s[k+1,n]" role="presentation" style="position: relative;">s[k+1,n]$s[k+1,n]$在F(x−2)" role="presentation" style="position: relative;">F(x−2)$F(x-2)$中出现的次数

我们定义状态dp[i][l][r]" role="presentation" style="position: relative;">dp[i][l][r]$dp[i][l][r]$表示s[l,r]" role="presentation" style="position: relative;">s[l,r]$s[l,r]$在F(i)" role="presentation" style="position: relative;">F(i)$F(i)$的所有子序列中出现的次数。
那么 dp[i][l][r]+=dp[i−1][l][r]∗2len(F(i−2));当r==n时候" role="presentation" style="position: relative;">dp[i][l][r]+=dp[i−1][l][r]∗2len(F(i−2));当r==n时候$dp[i][l][r]+=dp[i-1][l][r]\ast 2^{len(F(i-2))};当r==n时候$

解释：当r==n的时候，由于s[l,r]已经在F(i-1)中结尾了，所以F(i-2)中可以随便选取组成新的字串。

dp[i][l][r]+=dp[i−1][l][r]∗1;当r!=n时候" role="presentation" style="position: relative;">dp[i][l][r]+=dp[i−1][l][r]∗1;当r!=n时候$dp[i][l][r]+=dp[i-1][l][r]\ast 1;当r!=n时候$

解释：当r!=n的时候，由于s[l,r]没有在F(i-1)中结尾，此时如果取F(i-2)中字符的话，会给后面造成影响，即拼接出的包含s不是连续的。

dp[i][l][r]+=dp[i−2][l][r]∗2len(F(i−1));当l==1时候" role="presentation" style="position: relative;">dp[i][l][r]+=dp[i−2][l][r]∗2len(F(i−1));当l==1时候$dp[i][l][r]+=dp[i-2][l][r]\ast 2^{len(F(i-1))};当l==1时候$
dp[i][l][r]+=dp[i−2][l][r]∗1;当l!=1时候" role="presentation" style="position: relative;">dp[i][l][r]+=dp[i−2][l][r]∗1;当l!=1时候$dp[i][l][r]+=dp[i-2][l][r]\ast 1;当l!=1时候$ 然后就是s[l,r]" role="presentation" style="position: relative;">