[ABC323E] Playlist 题解

FFTotoro · 2023-10-07 21:53:01 · 题解

设 f_i 为存在任意一首音乐正好在 i 时刻开始播放的概率。

如果存在一首歌时长是 t，可以有转移 f_{i+t}\leftarrow f_{i+t}+\dfrac{f_i}{N}：在 i 时刻有 \dfrac{1}{N} 的概率播放了这首歌，所以将其除以 N 再加到 f_{i+t} 里面。

什么条件下才会在 X+0.5 的时刻播放第一首歌呢？显然第一首歌要在 [X-T_0+1,X] 的时候开始播放才可能覆盖到 X+0.5 的时刻。对于这些时刻，每个时刻都有 \dfrac{1}{N} 的概率播放第一首歌，所以答案即为 \sum\limits_{i=X-T_0+1}^X\dfrac{f_i}{N}。

除法可用费马小定理求乘法逆元实现。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%mod*a%mod;
    a=a%mod*a%mod; b>>=1;
  }
  return r;
}
int inv(int x){
  return qpow(x,mod-2);
} // 费马小定理求逆元
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,x,c=0; cin>>n>>x;
  vector<int> a(n),f(x+1);
  for(auto &i:a)cin>>i;
  int y=inv(n); f[0]=1; // 预处理
  for(int i=0;i<=x;i++){ // 枚举时刻
    for(int j=0;j<n;j++) // 枚举歌曲
      if(i+a[j]<=x)(f[i+a[j]]+=f[i]*y%mod)%=mod; // 进行转移
    if(i+a[0]>x)(c+=f[i]*y%mod)%=mod; // 累计答案
  }
  cout<<c<<endl;
  return 0;
}