/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1700 点
問題文
(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) に対し、長さ N の整数列 f(P) を以下のように定めます。
-
整数列 X を X=(P_1,P_2,\dots,P_N) で初期化し、 X が単調増加数列になるまで以下の操作を行い続ける。なお、任意の順列 P に対し、 X は有限回の操作によって単調増加数列になることが示せる。
- X_i > X_{i+1} を満たす最小の i\ (1 \leq i < N) を k とする。 X の k 項目を末尾に移動する。より正確には、 X を (X_1,X_2,\dots,X_{k-1},X_{k+1},X_{k+2},\dots,X_N,X_{k}) で置き換える。
一連の操作で整数 x が末尾に移動させられた回数を C_x とし、 f(P)=(C_1,C_2,\dots,C_N) と定める。
f(P) としてありうるものの種類数を素数 M で割った余りを求めてください。
制約
- 1 \leq N \leq 500
- 10^8 \leq M \leq 10^9
- M は素数
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
4 998244353
出力例 1
8
例えば P=(1,4,3,2) の場合、 X は X=(1,4,3,2) で初期化され、操作は以下のように行われます。
- X_1 \leq X_2 かつ X_2 > X_3 であるため、 X_2=4 が末尾に移動し、 X は (1,3,2,4) に変化する
- X_2=3 が末尾に移動し、 X は (1,2,4,3) に変化する
- X_3=4 が末尾に移動し、 X は (1,2,3,4) に変化する
1,2,3,4 が末尾に移動させられた回数はそれぞれ 0,0,1,2 回であるため、 f(P)=(0,0,1,2) となります。
入力例 2
71 998244353
出力例 2
473972314
入力例 3
300 923223991
出力例 3
333532467
Score : 1700 points
Problem Statement
For a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N), define a length-N integer sequence f(P) as follows.
-
Initialize an integer sequence X with X=(P_1,P_2,\dots,P_N). Repeat the following operation until X is a strictly increasing sequence. (It can be shown that X will be a strictly increasing sequence in a finite number of operations for any permutation P.)
- Let k be the smallest index i (1 \leq i < N) such that X_i > X_{i+1}. Move the k-th element of X to the end. More precisely, replace X with (X_1,X_2,\dots,X_{k-1},X_{k+1},X_{k+2},\dots,X_N,X_{k}).
Let C_x be the number of times an integer x is moved to the end during this series of operations. Then, define f(P)=(C_1,C_2,\dots,C_N).
Find the number, modulo a prime number M, of distinct sequences that can occur as f(P).
Constraints
- 1 \leq N \leq 500
- 10^8 \leq M \leq 10^9
- M is prime.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
4 998244353
Sample Output 1
8
For example, when P=(1,4,3,2), we initialize X=(1,4,3,2) and perform operations as follows:
- Since X_1 \leq X_2 but X_2 > X_3, the element X_2=4 is moved to the end, and X becomes (1,3,2,4).
- X_2=3 is moved to the end, and X becomes (1,2,4,3).
- X_3=4 is moved to the end, and X becomes (1,2,3,4).
The number of times 1,2,3,4 are moved to the end is 0,0,1,2, respectively, so f(P)=(0,0,1,2).
Sample Input 2
71 998244353
Sample Output 2
473972314
Sample Input 3
300 923223991
Sample Output 3
333532467