ACM模版

描述

题解

一道十分不错的dp，越发的感觉我的dp好垃圾啊~~~关键是递推思维。

官方题解：

本题的关键点是发现如果我能在第i轮打败怪物j，那么我一定能在第i+1轮打败怪物j(前提是我还活着)。
因此我们可以通过递推来做这题。
令dp[i]表示第i轮我仍然存活时的方案综述，这里lyk的能量也必然为i。
显然dp[0]=n!。因为不管怎么排列，第0轮总是能存活的。
找到那些可以打败的怪物数量x，其中这些怪物已经被打败i个。
此时第i+1轮我仍然能存活的概率为(x-i)/(n-i)，只要将这个概率乘上dp[i]就能知道dp[i+1]的值。

这里除法可以用逆元来处理。
时间复杂度为线性。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

int n;
ll dp[MAXN];
int a[MAXN];

void init()
{
    ll res = 1;
    for (int i = 1; i <= n; i++)
    {
        res = (res * i) % MOD;
    }
    dp[0] = res;
}

ll exp_mod(ll a, ll b)
{
    ll res = 1;
    while (b != 0)
    {
        if (b & 1)
        {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

void input()
{
    int i, temp;
    scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
        scanf("%d", &temp);
        a[temp]++;
    }
}

void solve()
{
    int i;
    ll res = 0;
    for (i = 1; i <= n; i++)
    {
        a[i] = a[i] + a[i - 1];
    }
    for (i = 0; i <= n; i++)
    {
        // 已经击败i个
        ll t = exp_mod(n - i, MOD - 2) % MOD;   // 求逆元
        dp[i + 1] = ((dp[i] * (a[i] - i)) % MOD) * t % MOD;
    }
    for (i = 1; i <= n; i++)
    {
        ll s = (dp[i - 1] - dp[i] + MOD) % MOD; // 在第i轮被击败的情况
        res = (res + s * (i - 1) % MOD) % MOD;
    }
    res = (res + (dp[n] * n) % MOD) % MOD;
    cout << res;
}

int main()
{
    input();
    init();

    solve();

    return 0;
}