No.829 Growth Function Inflation
タグ : / 解いたユーザー数 18
作問者 :
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$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。