AtCoder Beginner Contest 378
翻译中…
Problem Statement
翻译中…
You are given integers $A$, $B$, and $M$.
翻译中…
How many permutations $P = (P_1, \dots, P_{AB-1})$ of $(1, 2, \ldots, AB - 1)$ satisfy all of the following conditions? Find the count modulo $M$.
翻译中…
- The length of a longest increasing subsequence of
$P$is$A$. - The length of a longest decreasing subsequence of
$P$is$B$. - There exists an integer
$n$such that appending$n + 0.5$to the end of$P$does not change either of the lengths of a longest increasing subsequence and a longest decreasing subsequence.
翻译中…
Constraints
翻译中…
- All input values are integers.
$2 \leq A, B$$AB \leq 120$$10^8 \leq M \leq 10^9$$M$is a prime.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
A B M翻译中…
Output
翻译中…
Print the number of permutations satisfying the conditions, modulo $M$.
翻译中…
样例
Input #1
3 2 998244353
Output #1
10
For example, $P = (2, 4, 5, 1, 3)$ satisfies the conditions. This can be confirmed as follows:
- The length of a longest increasing subsequence of $P$ is $3$.
- The length of a longest decreasing subsequence of $P$ is $2$.
- For $n = 4$, the lengths of longest increasing and decreasing subsequences of $(2, 4, 5, 1, 3, 4.5)$ are $3$ and $2$, respectively.
There are $10$ permutations of $(1, 2, 3, 4, 5)$ that satisfy the conditions.
Input #2
10 12 924844033
Output #2
623378361
Print the count modulo $M$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。