問題一覧 > 教育的問題

No.2975 単調増加部分積

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : 👑 p-adicp-adic / テスター : hamamuhamamu
0 ProblemId : 10058 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-12-02 20:11:04

注意

この問題の実行時間制限は10000[ms]です。

問題文

入力に MNM \leq N を満たす 22 個の正整数 N,MN, M と素数 PP が与えられます。

 

まず記法と用語の導入です。正整数列 AA に対し、AA の成分の総乗を Π(A)\Pi(A) と置きます。

NN 以下の相異なる正整数 MM 個からなる順列を (N,M)(N,M) 順列と呼ぶことにします。

(N,M)(N,M) 順列 AA に対し、AA の空列でない(連続部分列とは限らない)各狭義単調増加部分列 aa をわたる Π(a)\Pi(a) の総和を f(A)f(A) と置きます。

 

(N,M)(N,M) 順列は全部で NPM=N!(NM)!{}_N P_M = \frac{N!}{(N-M)!} 個あります。それらの中から (N,M)(N,M) 順列 AA をランダムに(どれが選ばれるかが等確率になるように)選ぶ時の f(A)f(A) の期待値の法 PP における値を求めてください。

なおここで有理数 xx の法 PP における値とは、以下の 22 条件を満たす一意な整数 rr を表します:

  • 0r<P0 \leq r < P である。
  • xx の既約分数表示を nd\frac{n}{d}dd は正整数、nndd と互いに素な整数)と表した時、ndr(modP)n \equiv dr \pmod{P} である。

ただしこのような rr が存在する必要十分条件は上記の ddPP が互いに素であることです。また整数 \ellmm が互いに素であるとは、\ellmm を共に割り切る正整数が 11 のみであるということです。

入力

入力は以下の形式で標準入力から 11 行で与えられます:

  • 11 行目に N,M,PN, M, P が半角空白区切りで与えられます。
NN MM PP

制約

入力は以下の制約を満たします:

  • NN1N96001 \leq N \leq 9600 を満たす整数である。
  • MM1MN1 \leq M \leq N を満たす整数である。
  • PPN<P109N < P \leq 10^9 を満たす素数である。

出力

f(A)f(A) の期待値の法 PP における値が一意に存在するならば、それを 11 行に出力してください。

そうでないならば、-1と出力してください。

最後に改行してください。

サンプル

サンプル1
入力
1 1 2
出力
1

(N,M)=(1,1)(N,M) = (1,1) であり、(N,M)(N,M) 順列 AA(1)(1) に限られます。(1)(1) の空列でない狭義単調増加部分列は (1)(1) 自身に限られ、Π((1))=1\Pi((1)) = 1 なので f((1))=1f((1)) = 1 です。

以上より f(A)f(A) は確率 1111 の値を取り、f(A)f(A) の期待値は 11 です。そして 11 の法 P=2P = 2 での値は 11 です。

サンプル2
入力
2 1 3
出力
0

(N,M)=(2,1)(N,M) = (2,1) であり、(N,M)(N,M) 順列 AA(1)(1)(2)(2)22 つです。サンプル1より f((1))=1f((1)) = 1 です。(2)(2) の空列でない狭義単調増加部分列は (2)(2) 自身に限られ、Π((2))=2\Pi((2)) = 2 なので f((2))=2f((2)) = 2 です。

以上より f(A)f(A) は確率 212^{-1}11 の値を取り、確率 212^{-1}22 の値を取ります。従って f(A)f(A) の期待値は 21×1+21×2=2132^{-1} \times 1 + 2^{-1} \times 2 = 2^{-1} 3 です。そして 2132^{-1} 3 の法 P=3P = 3 での値は 00 です。

サンプル3
入力
2 2 5
出力
4

(N,M)=(2,2)(N,M) = (2,2) であり、(N,M)(N,M) 順列 AA(1,2)(1,2)(2,1)(2,1)22 つです。(1,2)(1,2) の空列でない狭義単調増加部分列は (1),(2),(1,2)(1), (2), (1,2)33 つであり、それらの成分の総乗はそれぞれ 1,2,21, 2, 2 なので f((1,2))=1+2+2=5f((1,2)) = 1+2+2 = 5 です。(2,1)(2,1) の空列でない狭義単調増加部分列は (1),(2)(1), (2)22 つであり、それらの成分の総乗はそれぞれ 1,21, 2 なので f((2,1))=1+2=3f((2,1)) = 1+2 = 3 です。

以上より f(A)f(A) は確率 212^{-1}55 の値を取り、確率 212^{-1}33 の値を取ります。従って f(A)f(A) の期待値は 21×5+21×3=42^{-1} \times 5 + 2^{-1} \times 3 = 4 です。そして 44 の法 P=5P = 5 での値は 44 です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。