問題一覧 > 通常問題

No.829 Growth Function Inflation

レベル : / AI推定難易度 : 2225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : Pachicobue / テスター : kopricky
お気に入りにしたユーザー ProblemId : 2596 / 自分の提出
問題文最終更新日: 2019-05-03 23:24:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 213 (順位表) の他の問題:

Problem Statement

Aoki practices competitive programming every day, and so far he has taken part in contests for $N$ days and recorded his score for each day.
Letting the sequence of scores be $A=\{A_1,A_2,...,A_N\}$, Aoki apparently defines the "growth number $g(A)$" of the $N$ days as the number of $0 \le i \le N-1$ such that $\max\{A_1,A_2,...,A_i\} < A_{i+1}$.
Here, we define $\max(\emptyset)=-\infty$.
For example, the growth number of $A = \{1,2,1,2,4\}$ is 3 (note that he is considered to have "grown" on day 1 as well).

One day, due to an unforeseen accident, the dates of the score records were lost. He knows that the set of scores (duplicates allowed) is $\{S_1,S_2,...,S_N\}$, but the original order is now unknown.
In other words, it is known that the sequence of daily scores $\{A_1,A_2,...,A_N\}$ can be expressed as $A_i = S_{p_i}$ using a permutation $p$ of $\{1,2,..,,N\}$.
Below, we write $S(p):=\{S_{p_1}, S_{p_2},...,S_{p_N}\}$.

To gauge his own growth, Aoki wants to know the sum of the score function $\mathrm{SCORE}(p)=g(S(p)) \times B^{g(S(p))}$ over all permutations $p$ of $\{1,2,...,N\}$. Here, $B$ is a given positive integer.
Your task is to solve this problem on Aoki's behalf. Since the answer can be very large, report the remainder when it is divided by $10^9+7$.

Input

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

The first line contains the size $N$ of the score set $S$ and the value $B$ used in the definition of the score function, separated by a space.
The second line contains the elements of the score set $S$, separated by spaces.

Constraints
  • $1 \le N \le 2\times 10^5$
  • $1 \le B \lt 10^9+7$
  • $0 \le S_i \lt N$
  • All inputs are integers.

Output

Print on one line the remainder when the sum of $\mathrm{SCORE}(p)=g(S(p)) \times B^{g(S(p))}$ over the permutations $p$ of $\{1,2,...,N\}$ is divided by $10^9+7$.
Print a newline at the end.

Sample

Sample 1
Input
3 2
0 1 2
Output
52

The score order corresponding to each permutation is as follows:

  • $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$
The sum is $24+8+8+8+2+2=52$.

Sample 2
Input
2 1
1 1
Output
2

The permutations $p = \{0,1\}, \{1,0\}$ give the same score sequence $A=\{1,1\}$, but note that they are counted separately.

Sample 3
Input
6 548438800
2 3 3 1 0 2
Output
140476412

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