51 Nod 1670 打怪獸

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1670?打怪獸

lyk在玩一個叫做“打怪獸”的游戲。
游戲的規則是這樣的。
lyk一開始會有一個初始的能量值。每次遇到一個怪獸，若lyk的能量值>=怪獸的能量值，那么怪獸將會被打敗，lyk的能量值增加1，否則lyk死亡，游戲結束。
若怪獸全部打完，游戲也將會結束。
共有n個怪獸，由于lyk比較弱，它一開始只有0點能量值。
n個怪獸排列隨機，也就是說共有n!種可能，lyk想知道結束時它能量值的期望。
由于小數點比較麻煩，所以你只需要輸出期望*n!關于1000000007取模后的值就可以了！

?

例如有兩個怪獸，能量值分別為{0,1}，那么答案為2，因為游戲結束時有兩種可能，lyk的能量值分別為0和2。期望為1,1*2!=2，所以答案為2。

Input

第一行一個數n(1<=n<=100000)。
接下來一行n個數ai表示怪獸的能量(0<=ai<n)。

Output

一行表示答案

Input示例

2
0?1

Output示例

2

思路： 每輪打敗怪獸后 lyk的能量值加一  
　　　 所以 我們可以看出來 如果lyk在第i輪 打敗一個怪獸 那么在第i+1輪也一定可以打敗這個怪獸 
　　　 我們設 dp[i] 表示 lyk活到第 i 輪的概率  這時候lyk的能量 必然為i
　　　 顯然 第 i 輪 lyk一定存活 所以 dp[0] = N! %Mod
　　　 假設 我們已知 dp[i] 看一下怎么表示第 i+1輪的概率 
　　　 x 表示 有多少怪獸的能量小于等于 i+1 
　　　 到了 第 i+1 輪 只剩 (x-(i+1)+1) 只怪獸可以打 總的怪獸還剩 (n-(i+1)+1) 只
　　　 第i+1輪存活的概率記為 (x-(i+1)+1)/(n-(i+1)+1) 
　　　 那么到第 i+1 輪仍然存活的概率為 dp[i] *(x-(i+1)+1)/(n-(i+1)+1) 
　　　 除法用逆元來計算即可

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>

#define MAXN 50005

#define Mod 1000000007

using namespace std;

typedef long long LL;

LL num[100005],dp[100005];

LL Fast_Pow(LL a) {
    LL ret = 1, b = Mod - 2;
    while(b) {
        if (b & 1) ret = ( ret * a ) % Mod;
        a = ( a * a ) % Mod, b >>= 1;
    }
    return ret;
}

int main(int argc,char *argv[]) {
    int n; scanf("%d",&n);
    for(int i=0; i<n; ++i) scanf("%lld",num + i);
    
    sort(num,num + n);
    dp[0] = 1;
    for(int i=2; i<=n; ++i) dp[0] = (dp[0] * i) % Mod;
    
    int j = 0;
    for(int i=1; i<=n; ++i) {
        for(; i-1>=num[j] && j<n; ++j);
        dp[i] = dp[i-1] * (j - i + 1) % Mod * Fast_Pow((LL)n - i + 1) % Mod;
    }
    LL Ans = 0;
    for(int i=2; i<=n; ++i)
        Ans += (dp[i-1] - dp[i] + Mod) % Mod * ( i - 1 )% Mod;
    Ans = (Ans + dp[n] * n % Mod ) % Mod;
    printf("%lld\n",Ans);
    return 0;
}