链接：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]/.
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 .
输入描述:
The first line contains two integers, which are n and m.
The second line contains n integers. The i-th integer is p[i]. <= n <=
<= m <=
<= p[i] <=
输出描述:
You should output an integer, which is the answer.
示例1
输入 复制 输出 复制 说明 The exact answer is ( + + + + + + + ) / = /.
As * mod =
You should output .
备注:
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
解题思路：
我们假设一场游戏的一个子情况是0111011011，那么这个对结果的贡献是（3^m+2^m+2^m）*P（这种情况发生的概率）
将此式拆开==> 3^m*P+2^m*P+2^m*P
我们考虑3^m*P这部分，等价于3^m*P1*P2(P1为前五个点为01110的概率，P2为后面为11011的概率)，然后我们想一下，求最后的期望值，要算出所有的情况，那么其中就会有一些前五个点为01110的情况，那么这部分的和就为3^m*P1*(sum(p2,p3,p4......)),而sum(p2,p3,p4......)这部分等于1，因为后面的点将会发生所有情况，那么概率为1。而这只是算前五个点位01110的情况，我们还要算0110和11...和其他子情况的一段1，那么计算过程和上面是一样的，所以最后的结果就是将所有的连续1的序列的贡献求出来，累加一下就是答案。
如果你还是不懂
我给你举个例子：
0 0 | 0 1 q1*q2*q3*p4
1 0 | 0 1 p1*q2*q3*p4
1 1 | 0 1 p1*p2*q3*p4
0 1 | 0 1 q1*p2*q3*p4
此时遍历到最后一位是个1，这样前一位保证是0 ，对于有这种组合的所有数已经如上图排列，我们会发现其他地方即前两位是全排列，所以算这种情况的全排列的时候，（q1*q2+p1*q2+p1*p2+q1*p2）*q3*p4 ，括号内的值为1，所以这种情况的期望值就是1-n枚举连续1的情况。前一位和后一位为0的状态
#include<iostream>
#include<stdio.h>
using namespace std;
#define ll long long
const int mod =1e9+;
ll qsm(ll a,ll b)
{
ll ans=;
while(b>)
{
if(b%==)
{
ans=ans*a%mod;
}
b=b/;
a=a*a%mod;
}
return ans;
}
ll gailv1[];
ll gailv2[];
ll f[];
ll dp[][];
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
ll inv=qsm(,mod-);
for(int i=;i<=n;i++)
{
scanf("%lld",&gailv1[i]);
gailv2[i]=(-gailv1[i])*inv%mod;
gailv1[i]=gailv1[i]*inv%mod; } for(int i=;i<=n;i++)
{
f[i]=qsm(i,m);
} gailv2[]=*inv%mod;
gailv2[n+]=*inv%mod;
for(int i=;i<=n;i++)
{
dp[i][i]=gailv1[i];
for(int j=i+;j<=n;j++)
dp[i][j]=dp[i][j-]*gailv1[j]%mod;
}
ll ans=;
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
{ ans=(ans+dp[i][j]*f[j-i+]%mod*gailv2[i-]%mod*gailv2[j+]%mod)%mod;
} cout<<ans<<endl;
return ;
}