Description

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:

#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 asks: given some strings and the parameter $x$, what is the expectation of the answer $ans$?

$65537 = 2^{16} + 1$ is prime.

The parameter $x$ is fixed to $10$ in this program, but it will be provided in each input.

Input Format

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 Format

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.

2 2
aa
aa

32770

3 6
i
dont
know
what
to
say

58261

Hint

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