No.2975 Monotonically Increasing Subproduct
Note
The time limit for this problem is 10000[ms].
Problem Statement
You are given as input $2$ positive integers $N, M$ satisfying $M \leq N$, and a prime $P$.
First, we introduce some notation and terminology. For a sequence $A$ of positive integers, let $\Pi(A)$ denote the product of the elements of $A$.
We call a permutation consisting of $M$ distinct positive integers not greater than $N$ an $(N,M)$ permutation.
For an $(N,M)$ permutation $A$, let $f(A)$ be the sum of $\Pi(a)$ over all non-empty strictly increasing subsequences $a$ (not necessarily contiguous) of $A$.
There are ${}_N P_M = \frac{N!}{(N-M)!}$ $(N,M)$ permutations in total. When an $(N,M)$ permutation $A$ is chosen at random from among them (so that each one is chosen with equal probability), find the value modulo $P$ of the expected value of $f(A)$.
Here, the value modulo $P$ of a rational number $x$ means the unique integer $r$ satisfying the following $2$ conditions:
- $0 \leq r < P$.
- When $x$ is written in irreducible fraction form as $\frac{n}{d}$ ($d$ is a positive integer and $n$ is an integer coprime to $d$), $n \equiv dr \pmod{P}$.
Such an $r$ exists if and only if the above $d$ and $P$ are coprime. Integers $\ell$ and $m$ are said to be coprime if the only positive integer dividing both $\ell$ and $m$ is $1$.
Input
The input is given from standard input on $1$ line in the following format:
- The $1$st line contains $N, M, P$ separated by single spaces.
$N$ $M$ $P$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 9600$.
- $M$ is an integer satisfying $1 \leq M \leq N$.
- $P$ is a prime satisfying $N < P \leq 10^9$.
Output
If the value modulo $P$ of the expected value of $f(A)$ uniquely exists, print it on $1$ line.
Otherwise, print -1.
Print a newline at the end.
Sample
Sample 1
Input
1 1 2
Output
1
We have $(N,M) = (1,1)$, and the only $(N,M)$ permutation $A$ is $(1)$. The only non-empty strictly increasing subsequence of $(1)$ is $(1)$ itself, and $\Pi((1)) = 1$, so $f((1)) = 1$.
Therefore, $f(A)$ takes the value $1$ with probability $1$, and the expected value of $f(A)$ is $1$. The value of $1$ modulo $P = 2$ is $1$.
Sample 2
Input
2 1 3
Output
0
We have $(N,M) = (2,1)$, and the $(N,M)$ permutations $A$ are the $2$ permutations $(1)$ and $(2)$. By Sample 1, $f((1)) = 1$. The only non-empty strictly increasing subsequence of $(2)$ is $(2)$ itself, and $\Pi((2)) = 2$, so $f((2)) = 2$.
Therefore, $f(A)$ takes the value $1$ with probability $2^{-1}$ and the value $2$ with probability $2^{-1}$. Hence the expected value of $f(A)$ is $2^{-1} \times 1 + 2^{-1} \times 2 = 2^{-1} 3$. The value of $2^{-1} 3$ modulo $P = 3$ is $0$.
Sample 3
Input
2 2 5
Output
4
We have $(N,M) = (2,2)$, and the $(N,M)$ permutations $A$ are the $2$ permutations $(1,2)$ and $(2,1)$. The non-empty strictly increasing subsequences of $(1,2)$ are the $3$ subsequences $(1), (2), (1,2)$, whose products of elements are $1, 2, 2$ respectively, so $f((1,2)) = 1+2+2 = 5$. The non-empty strictly increasing subsequences of $(2,1)$ are the $2$ subsequences $(1), (2)$, whose products of elements are $1, 2$ respectively, so $f((2,1)) = 1+2 = 3$.
Therefore, $f(A)$ takes the value $5$ with probability $2^{-1}$ and the value $3$ with probability $2^{-1}$. Hence the expected value of $f(A)$ is $2^{-1} \times 5 + 2^{-1} \times 3 = 4$. The value of $4$ modulo $P = 5$ is $4$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu