LOJ 2541 「PKUWC2018」猎人杀——思路+概率+容斥+分治

时间：2024-07-17 17:37:08

题目：https://loj.ac/problem/2541

看了题解才会……有三点很巧妙。

1.分母如果变动，就很不好。所以考虑把操作改成 “已经选过的人仍然按 \( w_i \) 的概率被选，但是再次选中一个已经选过的人算作没有操作” 。

2.然后要容斥，考虑强制点集 S 的人在 1 号点之后被选、其余随意，那么

　　\( ans=\sum\limits_{S} (-1)^{|S|} \sum\limits_{i=0}^{\infty} (1-\frac{w_1 + w_S}{A})^i \frac{w_1}{A} \)

　　（其中 A 表示 \( \sum\limits_{i=1}^{n} w_i \) ，\( w_S \) 表示 \( \sum\limits_{i \in S} w_i \) ）

　　等比数列求和一下，就是 \( ans=\sum\limits_{S} (-1)^{|S|} \frac{w_1}{w_1+w_S} \)

3.注意到 \( \sum w <=1e5 \) ，所以考虑把那个式子里的分母看做多项式的次数！

　　那么算一个 \( \prod\limits_{i=2}^{n} (1-x^{w_i}) \)（这是考虑选出一个点集 S 的过程）

　　然后就是取 \( x^i \) 的系数 \( a_i \) ，给答案贡献 \( \frac{a_i}{w_1+i} \) ，最后答案再乘一个 \( w_1 \) 。

算那个连乘的式子，可以普通地分治。但注意到含有 k 个 w 的乘积式子的次数不是 k ，所以复杂度不是 \( T(n)=T(n/2)+O(nlogn) \) 。（可能是 n2logn？）

反正把 w 排个序再做就能了。不知道不排序是否也可以。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define vi vector<int>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=1e5+,M=(<<)+,mod=;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int pw(int x,int k)

{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;}

int n,w[N],len,r[M],wn[M],wn2[M],inv[M];

void ntt_pre(int n)

{

  for(len=;len<=n;len<<=);

  for(int R=;R<=len;R<<=)

    {

      wn[R]=pw(,(mod-)/R);

      wn2[R]=pw(,(mod-)-(mod-)/R);

      inv[R]=pw(R,mod-);

    }

}

void ntt(vi &a,bool fx)

{

  for(int i=;i<len;i++)

    if(i<r[i])swap(a[i],a[r[i]]);

  for(int R=;R<=len;R<<=)

    {

      int Wn=fx?wn2[R]:wn[R];

      for(int i=,m=R>>;i<len;i+=R)

    for(int j=,w=;j<m;j++,w=(ll)w*Wn%mod)

      {

        int x=a[i+j],y=(ll)w*a[i+m+j]%mod;

        a[i+j]=upt(x+y); a[i+m+j]=upt(x-y);

      }

    }

  if(!fx)return;  int iv=inv[len];

  for(int i=;i<len;i++)a[i]=(ll)a[i]*iv%mod;

}

vi solve(int L,int R)

{

  if(L==R)

    {

      vi ret; ret.resize(w[L]+);

      ret[]=; ret[w[L]]=-;

      return ret;

    }

  int mid=L+R>>;

  vi a=solve(L,mid), b=solve(mid+,R);

  int lm=a.size()-+b.size()-;

  for(len=;len<=lm;len<<=);

  for(int i=,j=len>>;i<len;i++)

    r[i]=(r[i>>]>>)+((i&)?j:);

  a.resize(len); b.resize(len);

  ntt(a,); ntt(b,);

  for(int i=;i<len;i++)a[i]=(ll)a[i]*b[i]%mod;

  ntt(a,);

  a.resize(lm+);

  return a;

}

int main()

{

  n=rdn(); int sm=;

  for(int i=;i<=n;i++)

    { w[i]=rdn(); if(i>)sm+=w[i];}//if!!!

  ntt_pre(sm);

  sort(w+,w+n+);//

  vi f=solve(,n); int ans=;

  for(int i=;i<=sm;i++)

    if(f[i])ans=(ans+(ll)f[i]*pw(upt(w[]+i),mod-))%mod;

  ans=(ll)ans*w[]%mod;

  printf("%d\n",ans);

  return ;

}

相关文章