首先需要算出第x+0.5秒后,第一首歌播放的概率
1.要在x+0.5秒后播放第一首,需要在x,x-1,x-2,...,x-t[1]+1,时就要开始播放第一首,并且概率是1/n,概率之和除以n
2.概率dp,dp[i]表示播放i的概率,那么可以转换成,dp[i]+=dp[i-j]/n%mod(i>=t[j])
3.答案就是x,x-1,...,x-t[1]+1概率之和再除以n
其次,因为要模上mod,模意义下的除法
1.根据乘法逆元可知,n* n^(mod-2)%mod=1
2.计算x/n,可以转换成x/n* (n* n^(mod-2))%mod==x* n^(mod-2)%mod
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=998244353;
int d[10005],t[10005];
int _pow(int a,int b=mod-2){
int ans=1;
while(b){
if(b&1) ans=(1LL*ans*a)%mod;//LL
a=1LL*a*a%mod;//开LL
b>>=1;
}
return ans;
}
int main(){
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>t[i];
int mo=_pow(n);
d[0]=1;
for(int i=1;i<=x;i++){
LL sum=0;
for(int j=1;j<=n;j++){
if(t[j]>i) continue;
sum=(sum+1LL*d[i-t[j]]*mo)%mod;//LL
}
d[i]=sum;
}
int ans=0;
for(int i=max(0,x-t[1]+1);i<=x;i++){
ans=(ans+d[i])%mod;
}
ans=1LL*ans*mo%mod;//LL
cout<<ans;
return 0;
}
- Beginner AtCoder Contest 323beginner atcoder contest 323 题解323 beginner atcoder contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 332 beginner atcoder contest 334