No.2975 単調増加部分積
タグ : / 解いたユーザー数 15
作問者 : 👑

注意
この問題の実行時間制限は10000[ms]です。
問題文
入力に を満たす 個の正整数 と素数 が与えられます。
まず記法と用語の導入です。正整数列 に対し、 の成分の総乗を と置きます。
以下の相異なる正整数 個からなる順列を 順列と呼ぶことにします。
順列 に対し、 の空列でない(連続部分列とは限らない)各狭義単調増加部分列 をわたる の総和を と置きます。
順列は全部で 個あります。それらの中から 順列 をランダムに(どれが選ばれるかが等確率になるように)選ぶ時の の期待値の法 における値を求めてください。
なおここで有理数 の法 における値とは、以下の 条件を満たす一意な整数 を表します:
- である。
- の既約分数表示を ( は正整数、 は と互いに素な整数)と表した時、 である。
ただしこのような が存在する必要十分条件は上記の と が互いに素であることです。また整数 と が互いに素であるとは、 と を共に割り切る正整数が のみであるということです。
入力
入力は以下の形式で標準入力から 行で与えられます:
- 行目に が半角空白区切りで与えられます。
制約
入力は以下の制約を満たします:
- は を満たす整数である。
- は を満たす整数である。
- は を満たす素数である。
出力
の期待値の法 における値が一意に存在するならば、それを 行に出力してください。
そうでないならば、-1
と出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 2
出力
1
であり、 順列 は に限られます。 の空列でない狭義単調増加部分列は 自身に限られ、 なので です。
以上より は確率 で の値を取り、 の期待値は です。そして の法 での値は です。
サンプル2
入力
2 1 3
出力
0
であり、 順列 は と の つです。サンプル1より です。 の空列でない狭義単調増加部分列は 自身に限られ、 なので です。
以上より は確率 で の値を取り、確率 で の値を取ります。従って の期待値は です。そして の法 での値は です。
サンプル3
入力
2 2 5
出力
4
であり、 順列 は と の つです。 の空列でない狭義単調増加部分列は の つであり、それらの成分の総乗はそれぞれ なので です。 の空列でない狭義単調増加部分列は の つであり、それらの成分の総乗はそれぞれ なので です。
以上より は確率 で の値を取り、確率 で の値を取ります。従って の期待値は です。そして の法 での値は です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。