← 返回题目列表

AtCoder · KeioPC2025_l

L. 许多最大连胜问题

中文机器翻译题面 查看原题

配点 : 101 点

問題文

Kemuniku 对连胜次数感兴趣,提出了以下问题。

最大连胜问题

正整数 N, M 和长度 N 序列 W, L 。

W_i = x 在 i \ (1 \le i \le N) 和“ i \lt j \le N 和 所有满足 L_j = x 在 j 不存在。” i 的数量 比方说 f(x) 。
此时 查找 \displaystyle \max_{1 \le x \le M} f(x) 。

但是,给定的序列 W, L 关于 1 \le W_i, L_i \le M 和 W_i \ne L_i 保证持有。

不过哈鲁伦觉得这道题太简单了,于是他想到了下一道题。

许多最大连胜问题

长度是 套装 N 序列 W, L 一群 最大连胜问题 的所有可能输入是 \big ( M \times (M - 1) \big ) ^ N 方法有很多。
关于所有这些 最大连胜问题 的答案总和 除以 P 后求余数。 请解决

许多最大连胜问题 。

制約

  • 1 \le N \le 300
  • 2 \le M \le 300
  • 10^8 \le P \le 10^9
  • P 是质数
  • 输入全为整数。

部分点

针对此问题设置了部分分数。

  • N, M \le 30 的数据集 1 点。 如果您正确回答

入力

输入将以以下格式从标准输入提供。

N \ M \ P

出力

打印答案。


入力例 1

2 2 998244353

出力例 1

6

最大连胜问题 的可能输入 (W, L) 如下 4 没错。

  • ((1, 1),(2, 2)) 那么答案是 2
  • ((1, 2),(2, 1)) 那么答案是 1
  • ((2, 1),(1, 2)) 那么答案是 1
  • ((2, 2),(1, 1)) 那么答案是 2

,所以答案是 6 。


入力例 2

7 7 202602157

出力例 2

123958978

入力例 3

46 35 924844033

出力例 3

88210081