链接：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

#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 ;

}