链接：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 81 The 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
解题思路：
我们假设一场游戏的一个子情况是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+7; ll qsm(ll a,ll b) { ll ans=1; while(b>0) { if(b%2==1) { ans=ans*a%mod; } b=b/2; a=a*a%mod; } return ans; } ll gailv1[1010]; ll gailv2[1010]; ll f[1010]; ll dp[1010][1010]; int main() { ll n,m; scanf("%lld%lld",&n,&m); ll inv=qsm(100,mod-2); for(int i=1;i<=n;i++) { scanf("%lld",&gailv1[i]); gailv2[i]=(100-gailv1[i])*inv%mod; gailv1[i]=gailv1[i]*inv%mod; } for(int i=1;i<=n;i++) { f[i]=qsm(i,m); } gailv2[0]=100*inv%mod; gailv2[n+1]=100*inv%mod; for(int i=1;i<=n;i++) { dp[i][i]=gailv1[i]; for(int j=i+1;j<=n;j++) dp[i][j]=dp[i][j-1]*gailv1[j]%mod; } ll ans=0; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) { ans=(ans+dp[i][j]*f[j-i+1]%mod*gailv2[i-1]%mod*gailv2[j+1]%mod)%mod; } cout<<ans<<endl; return 0; }