自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 22:24:13，当前版本为作者最后更新于2020-08-14 21:49:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

假设当前询问的$m_i$为$m$，$a_i$为第$i$个羊毛的颜色。

$Subtask\ 1:$

直接暴力枚举所有可能的子序列并用Hash/一些奇奇怪怪的方法判重。

时间复杂度$O(2^n*$判重的时间$)$。期望得分$5$分。

$Subtask\ 2$ && $3:$

考虑DP，$f_i$表示我们匹配到颜色序列第$i$位时的方案数。考虑再在后面添加一个$x$，假设$next_{i,x}$表示$i$右边最近的$x$的位置，则$f_{next_{x,i}}+=f_i$。

因为我们这种贪心匹配（每次选择最近的一个），所以不会计算重复。

时间复杂度$O(n*max \{ m_i\})$。期望得分$35$分。

$Subtask\ 4:$

我们这样只是将这个序列当成一个普通序列来做的，并没有利用其良好的性质。

我们考虑对于$x$，只有$x-m$，$x-m-1$，...，$x-1$会转移到$x$（因为更前面的点会转移到$x-m$）。

所以$f_i=f_{i-1}+f_{i-2}+...+f_{i-m}$，前缀和优化即可。

时间复杂度$O(n)$，期望得分$60$分。

$Subtask\ 5:$

假设$s_i=\sum_{j=1}^{i}f_j$，所以$s_i=2*s_{i-1}-s_{i-m-1}$，而我们要求的就是$s_n$。

可以考虑把这个问题转换成另一个问题：

从$0$出发走到$n$，有一个初始等于$1$的阈值$v$，有两种行动方式：

$1.$从$x$走到$x+1$，并让$v=2*v$。

$2.$从$x$走到$x+m+1$，并让 $v=-v$。

每次走到$n$之后，让初始为$0$的$ans+=v$。可以发现转换问题后$s_n=ans$（即跟原问题等价）。

可以发现$v$的值只跟两种行动方式的次数有关，所以考虑枚举行动方式$2$的次数，则可以得到：

$s_n=ans=\sum_{i=0}^{i\le \lfloor \frac{n}{m+1} \rfloor}2^{n-(m+1)*i}*(-1)^{i}* \binom{(n-(m+1)*i)+i}{i}$

(行动方式$2$走了$i$步，行动方式$1$会走$n-(m+1)*i$步，总共就会走$(n-(m+1)*i)+i$步)

可以对所有$m$直接暴力算出这个式子的值，这样时间复杂度是$n/1+n/2+...+n/n=O(nlogn)$的。期望得分$100$分。

总体来说本题应该是一道比较良心的签到题，有经验的OIer应该可以直接秒掉。出题人认为这题应该比A简单，但是书虫非要我放B /kk。

为啥那么多人会60不会100啊，这trick不是挺常见的嘛/fad。

upd：我才发现我上面的系数写反了，感谢@2016wudi的指出qwq。