1670 打怪兽

2023-11-22 13:05:38

1670 打怪兽题目来源：原创基准时间限制：1 秒空间限制：131072 KB 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 Output  一行表示答案
 Input示例  2
0 1
 Output示例  2
思路：dp+组合；
dp[i]表示能量为i时的前i个位置上符合要求的方案数，dp[i] = dp[i-1]*（sum[i-1]-(i-1)）;然后再乘法原理乘以后面的方案数，这时候i+1位置上只能放比i大的数，那么方案数为sum[n-1] - sum[i]，再乘以阶乘N[n-1-i]，复杂度O（n）;
   1 #include
 2 #include
 3 #include
 4 #include<string.h>
 5 #include
 6 #include
 7 using namespace std;
 8 typedef long long LL;
 9 const LL mod = 1e9+7;
10 LL N[100005];
11 int sum[100005];
12 LL dp[100005];
13 int main(void)
14 {
15     int n;
16     int d;
17     scanf("%d",&n);
18     memset(sum,0,sizeof(sum));
19     N[0] = 1;
20     for(int i = 0; i < n; i++)
21     {
22         scanf("%d",&d);
23         sum[d]++;
24     }
25     for(int i = 1; i < n; i++)
26     {
27         sum[i] += sum[i-1];
28         N[i] = N[i-1]*(LL)i%mod;
29     }
30     dp[0] = 1; LL ask = 0;
31     for(int i = 1;i <= n; i++)
32     {
33         dp[i] = dp[i-1]*(LL)(sum[i-1] - (i-1))%mod;
34         if(i == n)
35         {
36             ask = (ask +(LL)i*dp[i]%mod)%mod;
37         }
38         else
39         {
40             if(dp[i] <= 0)
41                 break;
42             else
43             {
44                 LL ak = sum[n-1] - sum[i];
45                 LL tp = N[n-1-i];
46                 ask = ask + (((LL)(i)*dp[i]%mod)*((ak%mod)*(tp%mod)%mod))%mod;
47                 ask%=mod;
48             }
49         }
50     }
51     printf("%lld\n",ask);
52     return 0;
53 }
      
 
转载于:https://www.cnblogs.com/zzuli2sjy/p/5848998.html
                        
                        
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！