Max History
题意翻译
我们定义 $f(a)$ 为:
1. 开始时,$f(a)=0$,$M=1$。
2. 对于每个 $2\le i\le n$,如果 $a_M<a_i$,那么 $f(a)=f(a)+a_M$,$M\gets i$。
现在对于一个给定的数组 $a$,求其所有排列的 $f(a)$ 之和,答案对 $10^9+7$ 取模。
**注意:** 如果两个元素的索引不同,那么它们被认为是不同的,因此对于每个数组 $a$,都恰好有 $n!$ 排列。
题目描述
You are given an array $ a $ of length $ n $ . We define $ f_{a} $ the following way:
- Initially $ f_{a}=0 $ , $ M=1 $ ;
- for every $ 2<=i<=n $ if $ a_{M}<a_{i} $ then we set $ f_{a}=f_{a}+a_{M} $ and then set $ M=i $ .
Calculate the sum of $ f_{a} $ over all $ n! $ permutations of the array $ a $ modulo $ 10^{9}+7 $ .
Note: two elements are considered different if their indices differ, so for every array $ a $ there are exactly $ n! $ permutations.
输入输出格式
输入格式
The first line contains integer $ n $ ( $ 1<=n<=1\ 000\ 000 $ ) — the size of array $ a $ .
Second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ).
输出格式
Print the only integer, the sum of $ f_{a} $ over all $ n! $ permutations of the array $ a $ modulo $ 10^{9}+7 $ .
输入输出样例
输入样例 #1
2
1 3
输出样例 #1
1
输入样例 #2
3
1 1 2
输出样例 #2
4
说明
For the second example all the permutations are:
- $ p=[1,2,3] $ : $ f_{a} $ is equal to $ 1 $ ;
- $ p=[1,3,2] $ : $ f_{a} $ is equal to $ 1 $ ;
- $ p=[2,1,3] $ : $ f_{a} $ is equal to $ 1 $ ;
- $ p=[2,3,1] $ : $ f_{a} $ is equal to $ 1 $ ;
- $ p=[3,1,2] $ : $ f_{a} $ is equal to $ 0 $ ;
- $ p=[3,2,1] $ : $ f_{a} $ is equal to $ 0 $ .
Where $ p $ is the array of the indices of initial array $ a $ . The sum of $ f_{a} $ is equal to $ 4 $ .