[容斥 NTT] LOJ#2541. 「PKUWC 2018」猎人杀

98 阅读 0 评论 65 点赞

我是靠谱客的博主激动唇彩，最近开发中收集的这篇文章主要介绍[容斥 NTT] LOJ#2541. 「PKUWC 2018」猎人杀，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

很妙的题

这题其实如果不考虑攻击的限制，也就是不管猎人死没死，他都能被当作攻击的目标，一个猎人被攻击到的概率是一样的。

设 $A=sum w_i$ ， $B$ 为已经死的猎人的 $w_i$ 的和，设 $P_i$ 为 $i$ 是下一个被杀死的概率（ $i$ 之前还活着）

那么 $P_i={w_iover A-B}$ ，如果不考虑攻击的限制，那么 $P_i={Bover A} P_i+{w_iover A}$

也就是有 $Bover A$ 的概率攻击到已经死的猎人，那么下一个杀死 $i$ 的概率还是 $P_i$ ，这个式子移项化简就变成了 $P_i={w_iover A-B}$

然后可以考虑容斥，枚举哪些人一定在1号后被杀死的，其他人随意

设 $S$ 为枚举到的人的 $w_i$ 的和

那么对答案的贡献就是 $(-1)^{text{人数}}sum_{i=0}^infty (1-{S+w_1over A})^i{w_1over A}=(-1)^{text{人数}}{w_1over S+w_1}$

那么对于每个 $S$ 可以背包求出系数，又因为 $S$ 不大，可以NTT优化转移

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef unsigned long long ull;
typedef vector<int> poly;

const int N=1000010,P=998244353;
const ull PP=1ULL*P*P;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void read(int &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

struct cmp{
  bool operator ()(poly a,poly b){
    return a.size()>b.size();
  }
};

priority_queue<poly,vector<poly>,cmp> Q;

inline int Pow(int x,int y){
  int ret=1;
  for(;y;y>>=1,x=1LL*x*x%P) if(y&1) ret=1LL*ret*x%P;
  return ret;
}

int n,num,b,a[N],rev[N],w[2][N];

inline void Pre(const int &n){
  int g=Pow(3,(P-1)/(num=n));
  w[0][0]=w[1][0]=1;
  for(int i=1;i<n;i++) w[1][i]=1LL*w[1][i-1]*g%P;
  for(int i=1;i<n;i++) w[0][i]=w[1][n-i];
}

inline void NTT(int *_a,int n,int r){
  static ull a[N];
  for(int i=0;i<n;i++) a[i]=_a[i];
  for(int i=1;i<n;i++) if(rev[i]>i) swap(a[i],a[rev[i]]);
  int *W=w[r];
  for(int i=1,t=1,ct=0;i<n;i<<=1,t++,ct++){
    for(int j=0;j<n;j+=(i<<1))
      for(int k=0;k<i;k++){
    ull x=a[j+k],y=a[j+k+i]%P*W[(num>>t)*k];
    a[j+k+i]=x+PP-y; a[j+k]+=y; 
      }
    if(!(ct&15)){
      for(int j=0;j<n;j++) a[j]%=P;
    }
  }
  if(!r) for(int i=0,iv=Pow(n,P-2);i<n;i++) a[i]=a[i]%P*iv;
  for(int i=0;i<n;i++) _a[i]=a[i]%P;
}

poly operator *(poly a,poly b){
  poly ret;
  if(a.size()*b.size()<=10000){
    ret.resize(a.size()+b.size()-1);
    for(int i=0;i<a.size();i++)
      for(int j=0;j<b.size();j++)
    ret[i+j]=(ret[i+j]+1LL*a[i]*b[j])%P;
    return ret;
  }
  int m,L=0; for(m=1;m<=(a.size()+b.size());m<<=1,L++); m<<=1;
  for(int i=1;i<m;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<L);
  static int A[N],B[N];
  for(int i=0;i<a.size();i++) A[i]=a[i];
  for(int i=0;i<b.size();i++) B[i]=b[i];
  NTT(A,m,1); NTT(B,m,1);
  for(int i=0;i<m;i++) A[i]=1LL*A[i]*B[i]%P;
  NTT(A,m,0); ret.resize(a.size()+b.size()-1);
  for(int i=0;i<ret.size();i++) ret[i]=A[i];
  for(int i=0;i<m;i++) A[i]=B[i]=0;
  return ret;
}

int main(){
#ifdef ljn
  freopen("1.in","r",stdin);
  freopen("1.out","w",stdout);
#endif
  read(n); read(b); n--; Pre(262144<<1);
  if(!n) return puts("0"),0;
  for(int i=1;i<=n;i++){
    read(a[i]); poly c;
    c.resize(a[i]+1); c[a[i]]=P-1; c[0]=1;
    Q.push(c);
  }
  while(Q.size()>1){
    poly A=Q.top(); Q.pop();
    poly B=Q.top(); Q.pop();
    Q.push(A*B);
  }
  poly t=Q.top(); int ans=0;
  for(int i=0;i<t.size();i++)
    ans=(ans+1LL*t[i]*Pow(i+b,P-2))%P;
  ans=1LL*ans*b%P;
  printf("%dn",ans);
  return 0;
}