Hash?

题目背景

**zhoutb2333**学习了哈希算法,他于是去统计给定一些字符串,其中有多少个本质不同的字符串。 但是**zhoutb2333**突发奇想,如果哈希采用的$base$每次随机,那么结果会变成什么样呢? **辣鸡出题人又出锅了!subtask3的数据有问题,现在统一将模数改为65537** 题目来源:[zhoutb2333](https://www.luogu.org/space/show?uid=31564)

题目描述

他通过某种办法,获得了一个函数:$int \ Rand(int \ x)$,它会等概率地返回一个$[0,x)$中的整数。 他写下了这样的代码: ``` cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int x=10,maxn=35,maxlen=16010; ll HASH[maxn]; const ll p=65537; char str[maxlen]; ll Hash(){ int base=Rand(x); ll ret=0; for(int i=1;str[i];i++) ret=(ret*base+str[i]-'a'+1)%p; return ret; } int main(){ int ans=0,n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%s",str+1),HASH[i]=Hash(); sort(HASH+1,HASH+n+1); HASH[0]=-1; for(int i=1;i<=n;i++) ans+=(HASH[i]!=HASH[i-1]); printf("%d\n",ans); return 0; } ``` **zhoutb2333**想问你,给定一些字符串和参数$x$,答案$ans$的期望是多少呢? $65537= 2^{16}+1$**是质数** **参数$x$在这个程序中是确定的$10$,但是每次输入会给定。**

输入输出格式

输入格式


第一行三个整数$x,N$,表示$base$生成的参数和字符串的个数 接下来$N$行每行一个字符串,字符串仅由小写字母组成。

输出格式


一行一个小数,表示答案$ans$的期望,**模$65537$输出**。 即:如果你的答案为$\frac{q}{p}$($gcd(p,q)=1$),那么输出使得$px \equiv q \ (mod \ 65537$的最小正整数$x$。可以证明答案$ans$一定为正有理数,并且这样的$x$一定存在。

输入输出样例

输入样例 #1

2 2
aa
aa

输出样例 #1

32770

输入样例 #2

3 6
i
dont
know
what
to
say

输出样例 #2

58261

说明

本题由$3$个$subtask$组成,设$M$为这$N$个字符串中,每个字符串长度的最大值。 对于$subtask \ 1$:$1 \le N \le 8 , M \le 10,x \le 4$,分值为$20$,时间限制为$1s$。 对于$subtask \ 2$:$1 \le N \le 30 , M \le 500,x \le 500$,分值为$50$,时间限制为$1s$。 对于$subtask \ 3$:$1 \le N \le 5 , M \le 16000,x \le 16000$,分值为$30$,时间限制为$4.5s$。 **样例#1解释:** 参数$x=2$,那么可能的哈希$base$为$0,1$。 如果哈希第一个`aa`采用的$base$和第二个`aa`的$base$相同,那么答案为$1$。 如果两个$base$不相同,那么答案为$2$。 分析发现这两种情况发生的概率相同,都是$\frac{1}{2}$,那么答案$ans$的期望为$1 * \frac{1}{2} + 2 * \frac{1}{2}=\frac{3}{2}$。使得$2x \equiv 3 \ (mod \ 65537)$的最小正整数$x$为$32770$。 **样例#2解释:** 求得答案为$\frac{53}{9}$。使得$9x \equiv 53 \ (mod \ 65537)$的最小正整数$x$为$58261$。 **注意:本题允许手动开$O2$优化以避免被卡常数,方法如下:** ``` cpp %:pragma GCC optimize(2) /*程序*/ ```