多校第九场 E Music Game 概率计数
本题题意：给出长度为n的序列a，表示每个点成功的概率，从1到n的分数计算方法是，若成功则获得连续成功的长度的m次方的分数，求最后的分数期望。
解法：咋看像是一个概率DP，实际上在支持n^2复杂度的情况下，我们只需要计算出所有单段连击的期望，然后求和就可以得到总的期望分数。
首先，预处理出每一段一直成功的概率。
然后我们可以枚举i,j表示在[i+1,j-1]区间内成功连击，并且由题目可知要计算上这段分数必须在i,j失败，结束连击，这段的期望就是(i失败的概率)*(j失败的概率)*([i+1,j-1]都成功的概率)。
为了方便计算，我们可以把0,n+1两点的成功概率设置成0。
以下为代码
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007,inv=570000004;
long long i,i0,n,m,T,a[1005],pre[1005][1005],mpow[1005],ans;
long long qpow(long long a,long long b,long long mod){long long r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
int main()
{
scanf("%lld %lld",&n,&m);
a[0]=a[n+1]=0,ans=0;
for(i=1;i<=n;i++)scanf("%lld",&a[i]),mpow[i]=qpow(i,m,mod);
for(i=1;i<=n;i++)
{
pre[i][i]=a[i]*inv%mod;
for(i0=i+1;i0<=n;i0++)pre[i][i0]=pre[i][i0-1]*a[i0]%mod*inv%mod;
}
for(i=0;i<=n;i++)
{
for(i0=i+2;i0<=n+1;i0++)
{
ans+=pre[i+1][i0-1]*mpow[i0-i-1]%mod*(100-a[i])%mod*inv%mod*(100-a[i0])%mod*inv%mod;
ans%=mod;
}
}
printf("%lld\n",ans);
return 0;
}
查看8道真题和解析
