P4235 Hash?
题目背景
**zhoutb2333**学习了哈希算法，他于是去统计给定一些字符串，其中有多少个本质不同的字符串。
但是**zhoutb2333**突发奇想，如果哈希采用的$base$每次随机，那么结果会变成什么样呢？
**辣鸡出题人又出锅了！subtask3的数据有问题，现在统一将模数改为65537**
题目来源：[zhoutb2333](https://www.luogu.org/space/show?uid=31564)
题目描述
他通过某种办法，获得了一个函数：`int Rand(int x)`，它会等概率地返回一个 $[0,x)$ 中的整数。
他写下了这样的代码：
```cpp
#include
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
输入格式
第一行三个整数 $x,N$，表示 $base$ 生成的参数和字符串的个数
接下来 $N$ 行每行一个字符串，字符串仅由小写字母组成。
输出格式
一行一个小数，表示答案 $ans$ 的期望，**模 $65537$ 输出**。
即：如果你的答案为 $\frac{q}{p}$（$\gcd (p,q)=1$），那么输出使得 $px \equiv q \pmod {65537}$ 的最小正整数 $x$。可以证明答案 $ans$ 一定为正有理数，并且这样的 $x$ 一定存在。
说明/提示
本题由 $3$ 个 $\text{subtask}$ 组成，设 $M$ 为这 $N$ 个字符串中，每个字符串长度的最大值。
对于 $\text{subtask} \ 1$：$1 \le N \le 8 , M \le 10,x \le 4$，分值为 $20$，时间限制为 $1s$。
对于 $\text{subtask} \ 2$：$1 \le N \le 30 , M \le 500,x \le 500$，分值为 $50$，时间限制为 $1s$。
对于 $\text{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 \ \pmod {65537}$ 的最小正整数 $x$ 为 $32770$。
**样例 #2 解释：**
求得答案为 $\frac{53}{9}$。使得 $9x \equiv 53 \ \pmod {65537}$ 的最小正整数 $x$ 为 $58261$。