网站优化怎么做 有什么技巧,广州企业网,软件开发流程包括哪些,久久建筑网免费下载怎么没有了1670 打怪兽lyk在玩一个叫做“打怪兽”的游戏。游戏的规则是这样的。lyk一开始会有一个初始的能量值。每次遇到一个怪兽#xff0c;若lyk的能量值怪兽的能量值#xff0c;那么怪兽将会被打败#xff0c;lyk的能量值增加1#xff0c;否则lyk死亡#xff0c;游戏结束。若… 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(1n100000)。
接下来一行n个数ai表示怪兽的能量(0ain)。 Output 一行表示答案 Input示例 2
0 1 Output示例 2思路 每轮打败怪兽后 lyk的能量值加一 所以 我们可以看出来 如果lyk在第i轮 打败一个怪兽 那么在第i1轮也一定可以打败这个怪兽 我们设 dp[i] 表示 lyk活到第 i 轮的概率 这时候lyk的能量 必然为i 显然 第 i 轮 lyk一定存活 所以 dp[0] N! %Mod 假设 我们已知 dp[i] 看一下怎么表示第 i1轮的概率 x 表示 有多少怪兽的能量小于等于 i1 到了 第 i1 轮 只剩 (x-(i1)1) 只怪兽可以打 总的怪兽还剩 (n-(i1)1) 只 第i1轮存活的概率记为 (x-(i1)1)/(n-(i1)1) 那么到第 i1 轮仍然存活的概率为 dp[i] *(x-(i1)1)/(n-(i1)1) 除法用逆元来计算即可 1 #includecstdio2 #includevector3 #includecstring4 #includeiostream5 #includealgorithm6 7 #define MAXN 500058 9 #define Mod 1000000007
10
11 using namespace std;
12
13 typedef long long LL;
14
15 LL num[100005],dp[100005];
16
17 LL Fast_Pow(LL a) {
18 LL ret 1, b Mod - 2;
19 while(b) {
20 if (b 1) ret ( ret * a ) % Mod;
21 a ( a * a ) % Mod, b 1;
22 }
23 return ret;
24 }
25
26 int main(int argc,char *argv[]) {
27 int n; scanf(%d,n);
28 for(int i0; in; i) scanf(%lld,num i);
29
30 sort(num,num n);
31 dp[0] 1;
32 for(int i2; in; i) dp[0] (dp[0] * i) % Mod;
33
34 int j 0;
35 for(int i1; in; i) {
36 for(; i-1num[j] jn; j);
37 dp[i] dp[i-1] * (j - i 1) % Mod * Fast_Pow((LL)n - i 1) % Mod;
38 }
39 LL Ans 0;
40 for(int i2; in; i)
41 Ans (dp[i-1] - dp[i] Mod) % Mod * ( i - 1 )% Mod;
42 Ans (Ans dp[n] * n % Mod ) % Mod;
43 printf(%lld\n,Ans);
44 return 0;
45 } 代码 转载于:https://www.cnblogs.com/whistle13326/p/7739636.html
