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)
/*程序*/
```