链接：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
#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
/*
题目大意：对于所有长度为n的01序列，
每一种对应一个计算权重的方法，
每一段连击都有其计算的权重。乍一看还以为是DP解法，想了一会儿觉得不可能，前段的状态
有一些不是线性递推可以转移过来的。
于是乎结合概率论的知识，这道题可以说是一个数学题。。。。可以验证，题目中所要求的期望，
就是每一段连续的连击（包含两端不连击）的期望，
基于这个结论，只要计数累加就行了。至于期望的这个性质，大体就是算法里面的贡献思维，
考虑单体长度对整体的贡献，
可以看到，单段的连续点击造成的影响，在整体看来只和
这一段有关，因为后面的所有情况概率和为1.*/const int maxn =3e3+5;
const ll mod=1e9+7,inv=570000004;ll powmod(ll x,ll y){ll t;for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod;return t;}ll n,m;
ll poss[maxn];
ll yu[maxn][maxn];
ll dp[maxn][maxn];int main()
{scanf("%lld%lld",&n,&m);poss[0]=poss[n+1]=0;for(int i=1;i<=n;i++) scanf("%lld",&poss[i]);for(int i=1;i<=n;i++){yu[i][i-1]=1;for(int j=i;j<=n;j++) yu[i][j]=yu[i][j-1]*poss[j]%mod*inv%mod;}ll ans=0;for(int i=0;i<=n+1;i++){for(int j=i+2;j<=n+1;j++){ll tp=yu[i+1][j-1]*powmod(j-i-1,m)%mod;tp=tp*(100LL-poss[i])%mod*inv%mod*(100LL-poss[j])%mod*inv%mod;///ans+=yu[i+1][j-1]*powmod(j-i-1,m)%mod*(100LL-poss[i])%mod*inv%mod*(100LL-poss[j])%mod*inv%mod;ans=(ans+tp)%mod;}}printf("%lld\n",ans);return 0;
}