2018牛客多校第九场E（动态规划，思维，取模）

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007,inv=570000004;
long long i,j,n,m,a[1010]/*成功几率*/,sum=0,dp[1010][1010]/*动态规划*/,def[1010]//预处理;
long long qpow(long long x,long long y,long long mod)//快速幂
{
    long long ans=1,tmp=x;
    while(y)
    {
        if(y&1)
            ans=ans*tmp%mod;
        tmp=tmp*tmp%mod;
        y>>=1;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    a[0]=0;
    a[n+1]=0;
    sum=0;
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        def[i]=qpow(i,m,mod);//预处理每段长度正确的分数
    }
    for(i=1;i<=n;i++)
    {
        dp[i][i]=a[i]*inv%mod;//单题成功率
        for(j=i+1;j<=n;j++)
        {
            dp[i][j]=dp[i][j-1]*a[j]%mod*inv%mod;//动态规划，i~j-1正确的基础上j题正确
        }
    }
    for(i=0;i<=n;i++)
    {
        for(j=i+2;j<=n+1;j++)
        {
            sum+=dp[i+1][j-1]*def[j-i-1]%mod*(100-a[i])%mod*inv%mod*(100-a[j])%mod*inv%mod;//i和j都不对而i+1~j-1正确
            sum%=mod;
        }
    }
    printf("%lld",sum);
    return 0;
}
//动态规划，思维，每进行一次运算都要进行取模

巴特西

2018牛客多校第九场E（动态规划，思维，取模）

最新文章

热门文章