AT_KeioPC2025_l Many Max Streak Problems

对连胜次数感兴趣的けむにく君出了一道如下题目。 > **Max Streak Problem** > > 给定正整数 $N, M$ 和长度为 $N$ 的数列 $W, L$。 > > 定义 $f(x)$ 为满足 $W_i = x$ 的所有 $i\ (1 \le i \le N)$，且不存在满足 $i < j \le N$ 且 $L_j = x$ 的 $j$ 的下标 $i$ 的个数。 > 现在，求 $\displaystyle \max_{1 \le x \le M} f(x)$。 > > 其中，给定的数列 $W, L$ 保证 $1 \le W_i, L_i \le M$ 且 $W_i \ne L_i$。 但はるるん君觉得这道题太简单，于是又想了如下问题。 > **Many Max Streak Problems** > > 作为 **Max Streak Problem** 输入的所有可能的 $W, L$ 序列对共有 $\big(M \times (M - 1)\big)^N$ 种。 > 对所有这些情况，计算 **Max Streak Problem** 的答案之和，再对 $P$ 取模。 请解答 **Many Max Streak Problems**。

输入通过标准输入按如下格式给出。 > $N\ M\ P$

输出答案。

## 部分分 本题包含部分分。 - 若你能对满足 $N, M \le 30$ 的情况给出正确答案，则可获得 $1$ 分。 ## 样例解释 1 所有可能的 $(W, L)$ 共有 $4$ 种。 - $((1, 1), (2, 2))$ 时，答案为 $2$。 - $((1, 2), (2, 1))$ 时，答案为 $1$。 - $((2, 1), (1, 2))$ 时，答案为 $1$。 - $((2, 2), (1, 1))$ 时，答案为 $2$。 因此，答案为 $6$。 ## 数据范围 - $1 \le N \le 300$ - $2 \le M \le 300$ - $10^8 \le P \le 10^9$ - $P$ 是素数 - 所有输入皆为整数。 由 ChatGPT 5 翻译