本文主要是介绍51nod-1670 打怪兽，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接
收藏 
关注 lyk在玩一个叫做“打怪兽”的游戏。
游戏的规则是这样的。
lyk一开始会有一个初始的能量值。每次遇到一个怪兽，若lyk的能量值>=怪兽的能量值，那么怪兽将会被打败，lyk的能量值增加1，否则lyk死亡，游戏结束。
若怪兽全部打完，游戏也将会结束。
共有n个怪兽，由于lyk比较弱，它一开始只有0点能量值。
n个怪兽排列随机，也就是说共有n!种可能，lyk想知道结束时它能量值的期望。
由于小数点比较麻烦，所以你只需要输出期望*n!关于1000000007取模后的值就可以了！
游戏的规则是这样的。
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
因此我们可以通过递推来做这题。
令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 <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#define maxn 50005
#define MOD 1000000007
using namespace std;
typedef long long ll;ll num[100005], dp[100005];
ll pow_mod(ll m){ll ans = 1, p = MOD - 2;while(p){if(p&1)(ans *= m) %= MOD;(m *= m) %= MOD;p >>= 1;}return ans;
}
int main(){// freopen("in.txt", "r", stdin);int n;scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%I64d", num+i);sort(num, num+n);dp[0] = 1;for(int i = 2; i <= n; i++)(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 * pow_mod((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 += dp[n] * n % MOD) %= MOD; printf("%I64d\n", ans);return 0;
}这篇关于51nod-1670 打怪兽的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
