当前位置: 代码迷 >> 综合 >> 牛客多校第九场 E Music Game 概率计数
  详细解决方案

牛客多校第九场 E Music Game 概率计数

热度:73   发布时间:2023-11-23 07:17:51.0

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

题目描述

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.

示例1

输入

复制

3 4
50 50 50

输出

复制

750000020

说明

000 0
001 1
010 1
011 16
100 1
101 2
110 16
111 81The exact answer is (0 + 1 + 1 + 16 + 1 + 2 + 16 + 81) / 8 = 59/4.
As 750000020 * 4 mod 1000000007 = 59
You should output 750000020.

备注:

If you don't know how to output a fraction mod 1000000007,
You may have a look at https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

本题题意:

给出长度为n的序列a,表示每个点成功的概率,

从1到n的分数计算方法是,若成功则获得连续成功的长度的m次方的分数,求最后的分数期望。

首先,预处理出每一段一直成功的的概率。

然后,枚举i,j表示出在[i+1,j-1]区间内成功连击,并且由题目可知要计算上这段分数必须在i,j失败,结束连击

这段的期望就是(i失败的概率)*(j失败的概率)*([i+1,j-1]都成功的概率)

为了方便计算,把0,n+1两个点的成功概率都设为0

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007,inv=570000004;
long long i,i0,n,m,T,a[1005],pre[1005][1005],mpow[1005],ans;
long long qpow(long long a,long long b,long long mod)
{long long r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
int main()
{scanf("%lld %lld",&n,&m);a[0]=a[n+1]=0,ans=0;for(i=1;i<=n;i++)scanf("%lld",&a[i]),mpow[i]=qpow(i,m,mod);for(i=1;i<=n;i++){pre[i][i]=a[i]*inv%mod;for(i0=i+1;i0<=n;i0++)pre[i][i0]=pre[i][i0-1]*a[i0]%mod*inv%mod;}for(i=0;i<=n;i++){for(i0=i+2;i0<=n+1;i0++){ans+=pre[i+1][i0-1]*mpow[i0-i-1]%mod*(100-a[i])%mod*inv%mod*(100-a[i0])%mod*inv%mod;ans%=mod;}}printf("%lld\n",ans);return 0;
}

 

  相关解决方案