/
実行時間制限: 6 sec / メモリ制限: 1024 MiB
Score: 100 points
Problem Statement
In JOI Kingdom, a national festival is held once a year. During the period of the festival, there are N events in total. The schedule for each event is already fixed. The schedule of the N events are described by sequences a, b of length N satisfying the following conditions.
- Every integer between 1 and 2N, inclusive, appears as an element of a or b.
- a_i < b_i (1 \le i \le N).
- a_i < a_{i+1} (1 \le i \le N - 1).
The i-th event will start at a_i minutes after the beginning of the festival, and end at b_i minutes after the beginning of the festival.
Participants of the festival may choose any events in which they will participate. However, it is not allowed to participate in two events whose schedules overlap. (Note that the starting times and the ending times of the events are different from each other.)
JOI-kun wants to participate in as many events as possible. Until last year, he chose the events in which he participated by the following procedures on a computer.
For i = 1, 2, \ldots, N, the following are done in this order.
If the schedule of the i-th event does not overlap the schedules of the other events in which he already chose to participate, he will participate in the i-th event. Otherwise, he will not participate in the i-th event.
However, after studying computer science, JOI-kun noticed that the above algorithm does not necessarily maximize the number of events in which JOI-kun will participate. From this year, JOI-kun will use an improved algorithm. Using the improved algorithm, JOI-kun will be able to maximize the number of events in which JOI-kun will participate.
JOI-kun wants to know the number of cases where the improved algorithm produces a larger number of events.
Write a program which, given the integer N and a large prime number P, calculates the number of pairs of sequences a, b describing the schedules of the N events for which the improved algorithm produces a larger number of events. Since the answer can be very large, your program should output the remainder of the answer when divided by P.
Input
Read the following data from the standard input.
N P
Output
Write one line to the standard output. The output should contain the remainder of the answer, the number of pairs of sequences a, b describing the schedules of the N events for which the improved algorithm produces a larger number of events, when divided by P.
Constraints
- 1 \le N \le 20\,000.
- 10^8 < P < 10^9.
- P is a prime number.
- Given values are all integers.
Subtasks
- (5 points) N \le 5.
- (5 points) N \le 8.
- (27 points) N \le 30.
- (14 points) N \le 300.
- (36 points) N \le 3\,000.
- (13 points) No additional constraints.
Sample Input 1
3 100000007
Sample Output 1
2
For example, consider the case where a = (1, 2, 4) and b = (6, 3, 5). If JOI-kun uses the algorithm used until last year, he will participate in the first event only. On the other hand, if he uses a correct algorithm to maximize the number of events, he will participate in the second event and the third event. Thus, he will participate in two events. In this case, the improved algorithm produces a larger number of events.
The following are the pair of sequences a, b for which the improved algorithm produces a larger number of events.
- a = (1, 2, 4), b = (6, 3, 5)
- a = (1, 2, 4), b = (5, 3, 6)
Therefore, output 2, which is the remainder of 2 when divided by 100\,000\,007.
This sample input satisfies the constraints of all the subtasks.
Sample Input 2
4 100000007
Sample Output 2
28
There are 28 pairs of sequences a, b satisfying the condition. Therefore, output 28, which is the remainder of 28 when divided by 100\,000\,007.
This sample input satisfies the constraints of all the subtasks.
Sample Input 3
15 999999937
Sample Output 3
935834920
There are 5\,295\,044\,602\,247\,148 pairs of sequences a, b satisfying the condition. Therefore, output 935\,834\,920, which is the remainder of 5\,295\,044\,602\,247\,148 when divided by 999\,999\,937.
This sample input satisfies the constraints of Subtasks 3, 4, 5, 6.
配点 : 100 点
問題文
JOI 国では,1 年に 1 回,国を挙げたお祭りが行われる.お祭りの期間中には N 個のイベントがあり,それぞれ開催時間が決まっている.N 個のイベントの開催時間は,以下の条件を満たす 2 つの長さ N の数列 a, b によって定められる.
- a, b の要素には,1 から 2N までのすべての整数がちょうど 1 回ずつ現れる.
- a_i < b_i (1 \leqq i \leqq N) である.
- a_i < a_{i+1} (1 \leqq i \leqq N - 1) である.
このとき,i 個目のイベントはお祭りの開始 a_i 分から,開始 b_i 分までの間開催される.
お祭りの参加者は,開催時間に重複部分がある 2 つのイベントに両方参加することはできないという条件のもとで,どのイベントに参加するかを自由に選べる.(各イベントの開始時刻と終了時刻は相異なることに注意せよ.)
JOI 君は,できる限り多くのイベントに参加したいと思い,去年まで以下のような処理をコンピュータで行うことで,参加するイベントを決めていた.
i = 1, 2, \ldots, N について,順に以下のことを行う.
i 個目のイベントの開催時間が,今までに参加すると決めたどのイベントの開催時間とも重複部分を持たないならば,i 個目のイベントに参加することを決める.そうでなければ i 個目のイベントには参加しないことにする.
ところが,情報科学を勉強した JOI 君は,このアルゴリズムでは必ずしも参加するイベントの数を最大化できないことに気づき,今年からは参加するイベントの数を正しく最大化するアルゴリズムを使うことにした.
JOI 君は,この改善によって参加するイベントが増える場合がどの程度あるのかを知りたい.
整数 N と大きな素数 P が与えられるので,N 個のイベントの開催時間を定める数列 a, b の組としてあり得るもののうち,アルゴリズムの改善により参加するイベントの数が増えるようなものの個数を P で割った余りを求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N P
出力
標準出力に,N 個のイベントの開催時間を定める数列 a, b の組としてあり得るもののうち,アルゴリズムの改善により参加するイベントの数が増えるようなものの個数を P で割った余りを 1 行で出力せよ.
制約
- 1 \leqq N \leqq 20\,000.
- 10^8 < P < 10^9.
- P は素数である.
- 入力される値はすべて整数である.
小課題
- (5 点) N \leqq 5.
- (5 点) N \leqq 8.
- (27 点) N \leqq 30.
- (14 点) N \leqq 300.
- (36 点) N \leqq 3\,000.
- (13 点) 追加の制約はない.
入力例 1
3 100000007
出力例 1
2
例えば a = (1, 2, 4),b = (6, 3, 5) の場合,JOI 君が去年まで使っていたアルゴリズムでは 1 個目のイベントのみに参加することになる.一方で,参加するイベントの数を正しく最大化するアルゴリズムを使うと,2 個目のイベントと 3 個目のイベントの 2 つに参加することができるので,アルゴリズムの改善により参加するイベントの数が増える.
このようにアルゴリズムの改善により参加するイベントの数が増えるような数列 a, b の組は以下の 2 個である.
- a = (1, 2, 4),b = (6, 3, 5)
- a = (1, 2, 4),b = (5, 3, 6)
よって,2 を 100\,000\,007 で割った余りである 2 を出力する.
この入力例はすべての小課題の制約を満たす.
入力例 2
4 100000007
出力例 2
28
条件を満たす数列 a, b の組は 28 個あるので,28 を 100\,000\,007 で割った余りである 28 を出力する.
この入力例はすべての小課題の制約を満たす.
入力例 3
15 999999937
出力例 3
935834920
条件を満たす数列 a, b の組は 5\,295\,044\,602\,247\,148 個あるので,これを 999\,999\,937 で割った余りである 935\,834\,920 を出力する.
この入力例は小課題 3, 4, 5, 6 の制約を満たす.