自动搬运

查看原文

来自洛谷，原作者为

	菲斯斯夫斯基 几时归去，作个闲人。对一张琴，一壶酒，一溪云。

搬运于2025-08-24 22:56:16，当前版本为作者最后更新于2024-05-07 10:47:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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$ 枚举的是散块的长度。任意一个整块和任意一个散块合并都会产生贡献，所以用到乘法原理。

$s$ 数组的转移是类似的：$s_i=\sum\limits_{j=1}^{i-1}s_{i-j-1}\times num_{j,1}$。

好了，现在散块和整块的价值都计算完毕。最后的价值不为 $0$ 的序列是由一个整块和散块合并而成的，枚举整块的长度即可：

$$ans_i=\sum\limits_{j=2}^{i}dp_j\times(num_{i-j,0}+num_{i-j,1}) $$

注意散块贡献的是个数而不是价值。

如果你觉得这篇题解写的不错，可以留下一个点赞，谢谢~

代码

代码的实现并没有难度，把上面的几个转移方程搬上去就行。

#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;
}