牛客网暑期ACM多校训练营（第九场） E（Music Game）

本文主要是介绍牛客网暑期ACM多校训练营（第九场） E（Music Game），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
Niuniu likes to play OSU!
We simplify the game OSU to the following problem.

Given n and m, there are n clicks. Each click may success or fail.
For a continuous success sequence with length X, the player can score X^m.
The probability that the i-th click success is p[i]/100.
We want to know the expectation of score.
As the result might be very large (and not integral), you only need to output the result mod 1000000007.
输入描述:
The first line contains two integers, which are n and m.
The second line contains n integers. The i-th integer is p[i].

1 <= n <= 1000
1 <= m <= 1000
0 <= p[i] <= 100
输出描述:
You should output an integer, which is the answer.

输入

3 4
50 50 50
输出

750000020

题意：给出n种物品，每种物品有p[i]/100的概率被选中，一种被选中的情形得分为其连续被选的物品数的m次方。看样例解释吧

链接：https://www.nowcoder.com/acm/contest/147/E
来源：牛客网

3 4

50 50

000 0
001 1 //1^4
010 1
011 16 //2^4
100 1
101 2 //(1^4)+(1^4)
110 16
111 81 //(3^4)

The exact answer is (0 + 1 + 1 + 16 + 1 + 2 + 16 + 81) / 8 = 59/4. //每一种的情形发生的概率为(1/2)*(1/2)*(1/2)
As 750000020 * 4 mod 1000000007 = 59
You should output 750000020.

思路：枚举开始点与终点的情形，维护概率dp，然后算出期望值ans

代码：

#include<bits/stdc++.h>
#define PI acos(-1)
#define ll long long
#define inf 0x3f3f3f3f
#define ull unsigned long long
using namespace std;
const ll mod=1e9+7;
long long qpow(long long a,long long b)
{
a=a%mod;
long long ans=1;
while(b)
{
if(b&1)
{
ans=(ans*a)%mod;
b--;
}
b>>=1;
a=a*a%mod;
}
return ans;
}
ll a[1005],b[1005],p[1005];
int main()
{
ll n,m;
ll inv=qpow(100,mod-2);
while(scanf("%lld%lld",&n,&m)!=EOF)
{
ll x;
a[0]=0;
a[n+1]=0;
b[0]=1;
b[n+1]=1;
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
a[i]=x*inv%mod;
b[i]=(100-x)*inv%mod;
}
for(int i=1;i<=n;i++) p[i]=qpow(i,m);
ll q;
ll ans=0;
for(int i=1;i<=n;i++)
{
q=b[i-1];
for(int j=i;j<=n;j++)
{
q=q*a[j]%mod;
ans=((q*b[j+1]%mod*p[j-i+1])%mod+ans)%mod;
}
}
cout<<ans<<endl;
}
}