Four, (50 points) Given a prime number $p$ and a natural number $n$, where $p \geqslant n \geqslant 3$. The set $A$ consists of sequences of length $n$ with elements taken from the set $\{1,2, \cdots, p-1\}$. If for any two sequences $\left(x_{1}, x_{2}, \cdots, x_{n}\right)$ and $\left(y_{1}, y_{2}, \cdots, y_{n}\right)$ in set $A$, there exist three distinct positive integers $k, l, m$ such that $x_{k} \neq y_{k}, x_{l} \neq y_{l}, x_{m} \neq y_{m}$. Find the maximum number of elements in set $A$.
For any two different sequences in set $A$, the first $n-2$ components cannot be completely the same (otherwise they would have at most 2 corresponding components different). Each component has $p$ possible values, so $\operatorname{card} A \leqslant p^{n-2}$. On the other hand, let the elements of $A$ be $\left(x_{1}, x_{2}, \cdots, x_{n}\right)$ where $x_{1}, x_{2}, \cdots, x_{n-2}$ take all $p^{n-2}$ different values, and let $x_{n-1} \equiv \sum_{i=1}^{n-2} x_{i}(\bmod p)$, and $x_{n} \equiv \sum_{i=1}^{n-2} i x_{i}(\bmod p)$, resulting in a $p^{n-2}$ element set $A$.

For any two different sequences $x=\left(x_{1}, x_{2}, \cdots, x_{n}\right)$ and $y=\left(y_{1}, y_{2}, \cdots, y_{n}\right)$ in $A$, $\left(x_{1}, x_{2}, \cdots, x_{n-2}\right) \neq \left(y_{1}, y_{2}, \cdots, y_{n-2}\right)$.
(1) If $\left(x_{1}, x_{2}, \cdots, x_{n-2}\right)$ and $\left(y_{1}, y_{2}, \cdots, y_{n-2}\right)$ have 3 corresponding components different, then $x$ and $y$ have at least 3 corresponding components different.
(2) If $\left(x_{1}, x_{2}, \cdots, x_{n-2}\right)$ and $\left(y_{1}, y_{2}, \cdots, y_{n-2}\right)$ have only 1 corresponding component $x_{k} \neq y_{k}(1 \leqslant k \leqslant n-2)$.
Then by $1 \leqslant\left|y_{k}-x_{k}\right|, k<p$ we get $y_{n-1}-x_{n-1} \equiv y_{k}-x_{k} \neq 0(\bmod p)$,
$y_{n}-x_{n} \equiv k\left(y_{k}-x_{k}\right) \neq 0(\bmod p)$. Hence $x_{n-1} \neq y_{n-1}, x_{n} \neq y_{n}$. $x$ and $y$ have 3 corresponding components different.
(3) If $\left(x_{1}, x_{2}, \cdots, x_{n-2}\right)$ and $\left(y_{1}, y_{2}, \cdots, y_{n-2}\right)$ have only 2 corresponding components $x_{k} \neq y_{k}, x_{m} \neq y_{m}(1 \leqslant k<m \leqslant n-2)$. Assume at this point $x_{n-1}=y_{n-1}, x_{n}=y_{n}$, then
$$
x_{k}+x_{m} \equiv y_{k}+y_{m}(\bmod p), k x_{k}+m x_{m} \equiv k y_{k}+m y_{m}(\bmod p).
$$

From the above two equations, we get $(m-k) x_{m} \equiv(m-k) y_{m}(\bmod p)$. But $1 \leqslant m-k<p$, which leads to $x_{m} \equiv y_{m}(\bmod p), x_{m}=y_{m}$. This contradicts the assumption. Therefore, at this point $x$ and $y$ also have 3 corresponding components different. In summary, the elements of set $A$ can have at most $p^{n-2}$ elements.