P10259 [COCI 2023/2024 #5] Piratski kod 题解
菲斯斯夫斯基
·
·
题解
P10259 [COCI 2023/2024 #5] Piratski kod 题解
upd：无聊的时候突然发现有一条转移方程写错了。
前言
非常好 dp，使我的大脑旋转。仍然是教练放在模拟赛里的题，考场时一眼没思路就跳了。结果其他大佬都是一眼秒，输了。/kk
思路
感觉应该还是可以看出来要用 dp 的，但是难在设计状态。
便于描述，以下将「没有两个连续的 1 的序列」称为「散块」；将「末尾的两个字符都是 1 的序列」称为「整块」。
不难发现一个价值不为 0 的二进制序列其实就是一个整块加上一个散块。
所以问题转化为如何求散块和整块的价值。
按照套路，我们设计 f_{i,0/1} 的含义为 长度为 i 的散块，结尾为 0/1 的价值总和。注意这里是价值总和，例如长度为 2，结尾为 0 求的就是 00 和 10 的价值之和。
考虑怎么转移。显然转移应该从 f_{i-1,0/1} 增加 0/1 得到 f_{i,0/1}。增加一个 0 好办，因为不会增加价值，所以得到第一条转移方程：f_{i,0}=f_{i-1,0}+f_{i-1,1}。增加一个 1 会对每一条序列都增加 \text{Fib}_i 的价值。
注意到是每一条，所以还要再设计一个数组 num_{i,0/1}，意思是长度为 i，结尾为 0/1 的散块的个数。num 数组的转移是简单的，注意不能连续放两个 1 就行：num_{i,0}=num_{i-1,0}+num_{i-1,1}，num_{i,1}=num_{i-1,0}。
回到刚才 f 数组的转移，现在已经求出了序列的个数，转移方程就出来了：f_{i,1}=f_{i-1,0}+num_{i-1,0}\times \text{Fib}_{i+1}。注意一下 \text{Fib} 的下标。
好了，现在散块算完了，该算整块了。整块和散块的计算是类似的。定义 dp_i 为长度为 i 的整块的价值总和，s_i 为长度为 i 的整块个数。
根据上面对整块的定义，可以发现一个以 1 结尾的散块在末尾加上不计算价值的 1 就成为了整块。同时两个整块拼接在一起仍然是整块。所以为了避免重复计算或者漏算，计算 dp_i 时将这个整块拆分成一个 前面计算过的整块 和 一个 用散块加 1 形成的整块。
状态转移方程可以推理得到：
dp_i=\sum\limits_{j=1}^{i-1}f_j\times s_{i-j-1}+dp_{i-j-1}\times num_{j,1}
其中 j 枚举的是散块的长度。任意一个整块和任意一个散块合并都会产生贡献，所以用到乘法原理。
好了，现在散块和整块的价值都计算完毕。最后的**价值不为** $0$ 的序列是由一个整块和散块合并而成的，枚举整块的长度即可：
$$ans_i=\sum\limits_{j=2}^{i}dp_j\times(num_{i-j,0}+num_{i-j,1})$$
注意散块贡献的是**个数**而不是价值。
如果你觉得这篇题解写的不错，可以留下一个点赞，谢谢~
### 代码
代码的实现并没有难度，把上面的几个转移方程搬上去就行。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010,mod=1e9+7;
int n;
int f[N][2],num[N][2],dp[N],fib[N]={0,1,1},s[N];
signed main()
{
cin>>n;
for(int i=3;i<=n;i++)
fib[i]=fib[i-1]+fib[i-2],fib[i]%=mod;
num[0][0]=1;
for(int i=1;i<=n;i++)
{
f[i][0]=f[i-1][0]+f[i-1][1],f[i][0]%=mod;
f[i][1]=f[i-1][0]+fib[i+1]*num[i-1][0],f[i][1]%=mod;
num[i][0]=num[i-1][0]+num[i-1][1],num[i][0]%=mod;
num[i][1]=num[i-1][0];
}
s[0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
{
dp[i]+=f[j][1]*s[i-j-1]+dp[i-j-1]*num[j][1],dp[i]%=mod;
s[i]+=s[i-j-1]*num[j][1],s[i]%=mod;
}
for(int i=1;i<=n;i++)
{
int ans=0;
for(int j=2;j<=i;j++)
ans+=dp[j]*(num[i-j][0]+num[i-j][1]),ans%=mod;
printf("%lld ",ans);
}
return 0;
}
```