P4235 Hash?

zhoutb2333 learned hashing and decided to count how many essentially different strings there are among some given strings. But then zhoutb2333 had a sudden idea: if the hashing $base$ is chosen randomly each time, what will the result look like? The lousy problem setter broke it again! The testdata for subtask 3 had an issue, so the modulus is now uniformly changed to $65537$. Problem source: [zhoutb2333](https://www.luogu.org/space/show?uid=31564).

By some means, he obtained a function: `int Rand(int x)`, which returns an integer uniformly at random from $[0, x)$. He wrote the following code: ```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

The first line contains two integers $x, N$, denoting the parameter that generates the $base$ and the number of strings. The next $N$ lines each contain one string, consisting only of lowercase letters.

Output a single number on one line: the expectation of $ans$, output modulo $65537$. That is, if your answer is $\frac{q}{p}$ ($\gcd(p, q) = 1$), then output the smallest positive integer $x$ such that $p x \equiv q \pmod{65537}$. It can be proved that the answer $ans$ is always a positive rational number, and such an $x$ always exists.

This problem has $3$ $\text{subtask}$s. Let $M$ be the maximum length among these $N$ strings. For $\text{subtask} \ 1$: $1 \le N \le 8, \ M \le 10, \ x \le 4$, score $20$, time limit $1 \ \text{s}$. For $\text{subtask} \ 2$: $1 \le N \le 30, \ M \le 500, \ x \le 500$, score $50$, time limit $1 \ \text{s}$. For $\text{subtask} \ 3$: $1 \le N \le 5, \ M \le 16000, \ x \le 16000$, score $30$, time limit $4.5 \ \text{s}$. Sample #1 explanation: With parameter $x = 2$, the possible hash $base$ values are $0, 1$. If the first `aa` and the second `aa` use the same $base$ for hashing, then the answer is $1$. If the two $base$ values are different, then the answer is $2$. These two cases happen with the same probability, both $\frac{1}{2}$, so the expectation of $ans$ is $1 * \frac{1}{2} + 2 * \frac{1}{2} = \frac{3}{2}$. The smallest positive integer $x$ such that $2 x \equiv 3 \ \pmod{65537}$ is $32770$. Sample #2 explanation: The answer is $\frac{53}{9}$. The smallest positive integer $x$ such that $9 x \equiv 53 \ \pmod{65537}$ is $58261$. Translated by ChatGPT 5