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 翻译