【CF946-F】Fibonacci String Subsequences

Source and Judge

CF946-F

Problem

【Brief description】
定义 F(x) 为 F(x−1) 与 F(x−2) 的连接(其中 F(0)=”0”,F(1)=”1” )。
给出一个长度为n的01字符串 s ,询问 s 在 F(x) 的所有子序列中出现了多少次。
【Input】
第一行n和x
第二行字符串s
【Output】
如上
【Limited conditions】
1≤n≤100,0≤x≤100
【Sample input】
2 4
11
【Sample output】
14
【Sample explanation】
F(4)=10110
1011
10110
1 1
1 1 0
1 11
1 110
1 1
1 10
011
0110
11
110
好难想……

Record

30min
我会告诉你我看错两次题吗?

Analysis

请先思考后再展开

其实就是一个裸区间dp
f[i][l][r]表示F(i)的子序列中有多少个s[l,r]
然后就三种情况

  1. 从左边继承,f[i-1][l][r],次数默认1;若r=n,右边有2^{ln[i-2]}种选取方案(就是任选)
  2. 从右边继承,f[i-2][l][r],次数默认1;若l=1,左边有2^{ln[i-1]}种选取方案(就是任选)
  3. 从两边继承,f[i-1][l][k]*f[i-2][k+1][r],次数1

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int MAXN=110;
ll f[MAXN][MAXN][MAXN];
ll g[MAXN];
char s[MAXN];
int main()
{
int n,x;scanf("%d%d%s",&n,&x,s+1);
for(int i=1;i<=n;i++) f[s[i]=='1'][i][i]=1;
g[0]=2;g[1]=2;for(int i=2;i<=x;i++) g[i]=(g[i-1]*g[i-2])%MOD;
for(int i=2;i<=x;i++)
{
for(int l=1;l<=n;l++)
{
for(int r=l;r<=n;r++)
{
if(r==n) f[i][l][r]=(f[i][l][r]+f[i-1][l][r]*g[i-2]%MOD)%MOD;
else f[i][l][r]=(f[i][l][r]+f[i-1][l][r])%MOD;
if(l==1) f[i][l][r]=(f[i][l][r]+f[i-2][l][r]*g[i-1]%MOD)%MOD;
else f[i][l][r]=(f[i][l][r]+f[i-2][l][r])%MOD;
for(int k=l;k<=r-1;k++)
f[i][l][r]=(f[i][l][r]+f[i-1][l][k]*f[i-2][k+1][r]%MOD)%MOD;
}
}
}
printf("%lld",f[x][1][n]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6a8a.html
转载请注明出处,谢谢!