Hash? 题解

zhoutb2333 · 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)即可...比多点求值快不知道哪去了