問題一覧 > 通常問題

No.829 成長関数インフレ中

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : PachicobuePachicobue / テスター : koprickykopricky
1 ProblemId : 2596 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-05-03 23:24:48

問題文

青木くんは競技プログラミングの精進を毎日行っており，これまでに$N$日間コンテストに出てそれぞれの得点を記録していました。
得点数列を $A=\{A_1,A_2,...,A_N\}$ と仮定したとき、 青木くんは$N$日間の「成長数 $g(A)$ 」を $\max\{A_1,A_2,...,A_i\} < A_{i+1}$ となる $0 \le i \le N-1$ の個数と定義しているようです。
但し， $\max(\emptyset)=-\infty$ とします。
例えば $A = \{1,2,1,2,4\}$ の成長数は3です(1日目にも「成長した」とすることに注意して下さい)。

ある日不慮の事故で得点記録の日付が消えてしまい、得点の集合(重複を許す)が $\{S_1,S_2,...,S_N\}$ であることは分かるものの、 元の順番がわからなくなりました。
つまり各日の得点数列 $\{A_1,A_2,...,A_N\}$ は、$\{1,2,..,,N\}$ の順列 $p$ を用いて $A_i = S_{p_i}$ と表せることが分かっています．
以下， $S(p):=\{S_{p_1}, S_{p_2},...,S_{p_N}\}$ と記すことにします。

青木くんは自分の成長度を推し量るべく、 $\{1,2,...,N\}$ の順列 $p$ 全てに対するスコア関数 $\mathrm{SCORE}(p)=g(S(p)) \times B^{g(S(p))}$ の総和が知りたくなりました。 ここで $B$ は与えられる正の整数です。
あなたの仕事は青木くんの代わりにこの問題を解くことです。 但し、答えは非常に大きくなりうるので $10^9+7$ で割った余りを教えてあげて下さい。

入力

$N\ B$
$S_1\ S_2\ S_3\ \dots\ S_N$

1行目に得点集合 $S$ の大きさ $N$ 、スコア関数の定義に関わる値 $B$ が空白区切りで与えられます。
2行目に得点集合 $S$ の要素が空白区切りで与えられます。

制約
  • $1 \le N \le 2\times 10^5$
  • $1 \le B \lt 10^9+7$
  • $0 \le S_i \lt N$
  • 入力は全て整数である。

出力

$\{1,2,...,N\}$ の順列 $p$ に対する $\mathrm{SCORE}(p)=g(S(p)) \times B^{g(S(p))}$ の総和を$10^9+7$で割った余りを一行に出力して下さい。
最後に改行して下さい。

サンプル

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

各順列に対応する得点順は

  • $A=\{0,1,2\} : g(A)=3,　\mathrm{SCORE}=3\times 2^3$
  • $A=\{0,2,1\} : g(A)=2,　\mathrm{SCORE}=2\times 2^2$
  • $A=\{1,0,2\} : g(A)=2,　\mathrm{SCORE}=2\times 2^2$
  • $A=\{1,2,0\} : g(A)=2,　\mathrm{SCORE}=2\times 2^2$
  • $A=\{2,0,1\} : g(A)=1,　\mathrm{SCORE}=1\times 2^1$
  • $A=\{2,1,0\} : g(A)=1,　\mathrm{SCORE}=1\times 2^1$
で、総和は$24+8+8+8+2+2=52$となります。

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

順列$p = \{0,1\}, \{1,0\}$で得点数列は同じ$A=\{1,1\}$となりますが、区別して数えることに注意して下さい。

サンプル3
入力
6 548438800
2 3 3 1 0 2
出力
140476412

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