自动搬运

查看原文

来自洛谷，原作者为

	zhoutb2333 **

搬运于2025-08-24 21:57:58，当前版本为作者最后更新于2018-02-05 23:18:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

算法1：

考虑将所有字符串的所有哈希值计算出来。那么枚举每一种情况并统计即可。复杂度$O(NMx+x^N)$。

可以通过$subtask \ 1$，预期得分$20$分。

算法2：

仍然考虑将所有哈希值计算出来，但是统计答案时改为计算每个结果对$ans$的贡献。

等于$\sum ^{p-1}_{i=0}P(i$出现$)*1+P(i$不出现$)*0$

即$\sum ^{p-1}_{i=0}( 1- \prod ^{N}_{j=1} \frac{x-cnt[S_j][i]}{x})$，其中$S_j$表示第$j$个字符串，$x$表示$rand()$参数，$cnt[S_j][i]$表示$S_j$的哈希值中$i$出现的次数。复杂度$O(NMx)$。

可以通过$subtask \ 2$，预期得分$70$分。

算法3：

单独考虑一个字符串，下标从$1$开始。

设当前的$base=b$，$f[n]$表示$S$哈希到第$n$位的值。则有转移$f[n]=b*f[n-1]+S[n]$。那么我们会发现$f[\left| S \right|]$是一个关于$b$的多项式函数，设为$G(b)$。容易知道$G(b)=\sum ^{\left| S \right|}_{i=1} S[i]*b^{n-i}$

那么我们求的是$G(0),G(1) \dots G(x-1)$。可以用多项式多点求值做，复杂度$O(NSlog^2S),S=2^{\lceil log \ max(M,x) \rceil}$。

可以通过$subtask \ 3$，预期得分$100$分。

嗯..这是$p=998244353$的做法，下调成了$40961$是我出锅了。

如果是现在的$p=65537$还有一种很快的算法，就是将长度$M$强行设为$65536$后用一遍$DFT$带入求值。

因为$\frac{(p-1)}{M}=1$，所以做完$DFT$后数组里第$i$位是$G(g^i)$，然后$g^i$遍历$1$~$p-1$，所以最后再加上$G(0)$即可...比多点求值快不知道哪去了