題意

定義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]s[1,n]在F(x?1)F(x?1)中出現的次數乘以2len(F(x?2))2len(F(x?2))
• s[1,n]s[1,n]在F(x?2)F(x?2)中出現的次數乘以2len(F(x?1))2len(F(x?1))
• s[1,k]s[1,k]在F(x?1)F(x?1)中出現的次數*s[k+1,n]s[k+1,n]在F(x?2)F(x?2)中出現的次數

我們定義狀態dp[i][l][r]dp[i][l][r]表示s[l,r]s[l,r]在F(i)F(i)的所有子序列中出現的次數。
那么

dp[i][l][r]+=dp[i?1][l][r]?2len(F(i?2));當r==n時候dp[i][l][r]+=dp[i?1][l][r]?2len(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時候dp[i][l][r]+=dp[i?1][l][r]?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時候dp[i][l][r]+=dp[i?2][l][r]?2len(F(i?1));當l==1時候
dp[i][l][r]+=dp[i?2][l][r]?1;當l!=1時候dp[i][l][r]+=dp[i?2][l][r]?1;當l!=1時候

然后就是s[l,r]s[l,r]分兩段s[l,k]s[l,k]在F(i?1)F(i?1)里面和s[k+1,r]s[k+1,r]在F(i?2)F(i?2)里面。
dp[i][l][r]+=dp[i][l][k]?dp[i][k+1][r],l<=k<rdp[i][l][r]+=dp[i][l][k]?dp[i][k+1][r],l<=k<r

---

實現代碼

#include <iostream> #include <cstdio> using namespace std; #define pr(x) cout<<#x<<':'<<x<<endl typedef long long ll; const int maxn = 107; const ll mod = 1e9+7; ll dp[maxn][maxn][maxn]; char s[maxn]; int n,m; ll modpow2[maxn]; int main(){scanf("%d%d",&m,&n);scanf(" %s",s);modpow2[0] = modpow2[1] = 2;for(int i = 2;i <= n;++i)modpow2[i] = modpow2[i-1]*modpow2[i-2]%mod;for(int i = 0;i < m;++i){dp[s[i]-'0'][i+1][i+1] = 1;}for(int i = 2;i <= n;++i){for(int l = 1;l <= m;++l){for(int r = l;r <= m;++r){dp[i][l][r] += dp[i-1][l][r]*(r == m?modpow2[i-2]:1)%mod;dp[i][l][r] += dp[i-2][l][r]*(l == 1?modpow2[i-1]:1)%mod;for(int k = l;k < r;++k){dp[i][l][r] += dp[i-1][l][k]*dp[i-2][k+1][r]%mod;}dp[i][l][r] %= mod;}}}cout<<dp[n][1][m]<<endl;return 0; }

總結

以上是生活随笔為你收集整理的codeforces F.Fibonacci String Subsequences的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。