牛客网暑期ACM多校训练营（第九场） E Music Game

本文主要是介绍牛客网暑期ACM多校训练营（第九场） E Music Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.nowcoder.com/acm/contest/147/E

 

整体思路就是暴力求所有连续区间的概率

想着用前缀来做；

发现如果有一个概率是0的话，会影响后面的前缀积

于是就分块来求前缀即可

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long su[1111];
long long fa[1111];
long long qz[1111];
long long dp[1111];
long long ans[1111];
long long qpow(long long x,long long cs)
{long long ans=1;while(cs){if(cs&1)ans=ans*x%mod;x=x*x%mod;cs>>=1;}return ans;
}
void solve(int l,int r)
{qz[l-1]=0;qz[l]=su[l];for(int i=l+1;i<=r;i++)qz[i]=qz[i-1]*su[i]%mod;for(int i=1;i<=r-l+1;i++){for(int j=l;j<=r-i+1;j++){long long gg;if(j==l){gg=qz[j+i-1];}else gg=qz[j+i-1]*qpow(qz[j-1],mod-2)%mod;gg%=mod;gg=gg*fa[j-1]%mod;gg=gg*fa[j+i]%mod;dp[i]=(dp[i]+gg)%mod;}}
}
int main(){long long n,m;while(cin>>n>>m){int wz[1111];int js=0;memset(dp,0,sizeof(dp));ans[1]=1;for(int i=2;i<=n;i++)ans[i]=qpow(i,m);long long a;long long _100=qpow(100,mod-2);wz[0]=0;js++;for(int i=1;i<=n;i++){cin>>a;su[i]=a*_100%mod;fa[i]=(100-a);fa[i]=fa[i]*_100%mod;if(a==0){wz[js++]=i;}}wz[js++]=n+1;su[0]=su[n+1]=0;fa[0]=fa[n+1]=1;for(int i=0;i<js-1;i++){if(wz[i+1]-wz[i]>1){solve(wz[i]+1,wz[i+1]-1);}}long long ans1=0;for(int i=1;i<=n;i++){ans1=(ans1+ans[i]*dp[i]%mod)%mod;}cout<<ans1<<endl;}return 0;
}

 

这篇关于牛客网暑期ACM多校训练营（第九场） E Music Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---