题目传送门 qwq

设 $sum=\sum_{i}w_i,kill=\sum_{i 被杀死了}w_i$ ,则当前杀死猎人 $k$ 的概率为:
$$
P=\frac{w_k}{sum-kill}\
$$
然后很显然,假设一次可以选择的猎人集合并非活着的猎人集合而是全集,但是如果选到了被杀了的猎人,就在选一次,很显然这个对答案没有任何影响。

那么就可以得到:
$$
P=\frac{kill}{sum}P+\frac{w_k}{sum}\
$$
这个式子和上面也是等价的。

考虑容斥,考虑求出 $T$ 集合中的所有猎人都在 $1$ 号猎人后面死,剩下的猎人随便的概率,很显然因为剩下的猎人随便,总概率为 $1$ ,无需考虑,只需要考虑这些猎人对 $1$ 号猎人的贡献,设 $qwq=\sum_{i\in T}w_i$ 。

则有:
$$
\begin{aligned}
res&=(-1)^{|T|}\sum_{i=0}^{\infty}(\frac{sum-qwq-w_1}{sum})^i\frac{w_1}{sum}\\
&=(-1)^{|T|}\sum_{i=0}^{\infty}(1-\frac{qwq+w_1}{sum})^i\frac{w_1}{sum}\\
&=(-1)^{|T|}\frac{w_1}{sum}\sum_{i=0}^{\infty}(1-\frac{qwq+w_1}{sum})^i\\
\end{aligned}
$$
$1-\frac{qwq-w+1}{sum}$ 的意思就是随便选不选中 $1$ 和 $T$ 中的元素的概率,$i$ 是枚举选的次数。

然后,因为有:
$$
\sum_{i=0}^{\infty}p^i=\frac{1}{1-p},p\in(1,-1)
$$
所以:
$$
\begin{aligned}
res&=(-1)^{|T|}\frac{w_1}{sum}\sum_{i=0}^{\infty}(1-\frac{qwq+w_1}{sum})^i\\
&=(-1)^{|T|}\frac{w_1}{sum}\frac{1}{1-(1-\frac{qwq+w_1}{sum})}\\
&=(-1)^{|T|}\frac{w_1}{sum}\frac{sum}{qwq+w_1}\\
&=(-1)^{|T|}\frac{w_1}{qwq+w_1}\\
\end{aligned}
$$
最后:
$$
ans=\sum_{T\in S}(-1)^{|T|}\frac{w_1}{qwq+w_1}
$$
可喜可贺 [手动滑稽],我们得到了一个 $O(2^n)$ 的算法,期望得分 $20pts$。但是发现题目给定的范围和 $n$ 貌似没什么关系,而是和 $\sum_{i}w_i$ 有关…… 所以变化一下:
$$
ans=\sum_{qwq=0}^{sum}\frac{w_1}{qwq+w_1}\left(\sum_{T\in S}(-1)^{|T|}[\sum_{i\in T}w_i=qwq]\right)
$$
后面的容斥系数 $\left(\sum_{T\in S}(-1)^{|T|}[\sum_{i\in T}w_i=qwq]\right)$ 背包一下即可,于是就得到了一个 $O(n\times sum)$ 的算法,期望得分 $50pts$ 。


假设现在需要求出,只使用集合 $S$ 中的猎人的容斥系数。

考虑 $S$ 的一个子集 $T$ ,假设 $T$ 的容斥系数为多项式 $f_1$ ,$\rm{S-T}$ 的容斥系数为多项式 $f_2$ ,如果 $S$ 的容斥系数为多项式 $f$ ,则有:
$$
f(n)=\sum_{i=0}^{n}f_1(i)f_2(n-i)
$$
这可以直接 $\rm{NTT}$ 做到 $O(n\log n)$ 。

然后像建立线段树那样,每一次往上合并即可,时间复杂度 $O(n\log^2 n)$ .

也就是直接分治 $\rm{NTT}$ 即可 (注意这个分治不是 $cdq$ 分治).

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+5;
const int mod=998244353;

int n,w[N],sum[N],sta[35],top;
int g[35][N<<1],f[N<<1];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Poly {
    int filp[N<<1];
    inline int modpow(int x,int y,int res=1) {
        for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
        return res;
    }
    inline void NTT(int*f,int limit,short inv) {
        for(int i=0;i<limit;++i)
            if(i<filp[i]) swap(f[i],f[filp[i]]);
        for(int p=2;p<=limit;p<<=1) {
            int len=p>>1,tmp=modpow(3,(mod-1)/p);
            for(int k=0;k<limit;k+=p) {
                int buf=1;
                for(int l=k;l<k+len;++l,buf=1ll*buf*tmp%mod) {
                    int t=1ll*f[l+len]*buf%mod;
                    f[l+len]=(f[l]-t+mod)%mod,f[l]=(f[l]+t)%mod;
                }
            }
        }
        if(inv==1) return;
        int sl=modpow(limit,mod-2);reverse(f+1,f+limit);
        for(int i=0;i<limit;++i) f[i]=1ll*f[i]*sl%mod;
    }
}using namespace Poly;

inline void solve(int*f,int l,int r) {
    if(l==r) {
        f[0]=1,f[w[l]]=mod-1;
        return;
    }
    int lc,rc,mid=(l+r)>>1,len=1,cnt=0;
    lc=sta[top--],solve(g[lc],l,mid),
    rc=sta[top--],solve(g[rc],mid+1,r);
    while(len<=sum[r]-sum[l-1]) len<<=1,++cnt;
    for(int i=0;i<len;++i) filp[i]=(filp[i>>1]>>1)|((i&1)<<(cnt-1));
    NTT(g[lc],len,1),NTT(g[rc],len,1);
    for(int i=0;i<len;++i) f[i]=1ll*g[lc][i]*g[rc][i]%mod;
    NTT(f,len,-1);
    for(int i=0;i<len;++i) g[lc][i]=g[rc][i]=0;
    sta[++top]=lc,sta[++top]=rc;
}

int main() {
    IN(n);
    for(int i=1;i<=n;++i) IN(w[i]),sum[i]=sum[i-1]+w[i];
    for(int i=1;i<=30;++i) sta[++top]=i;
    solve(f,2,n);
    int ans=0,limit=sum[n]-w[1];
    for(int i=0;i<=limit;++i)
        ans=(ans+1ll*f[i]*w[1]%mod*modpow(w[1]+i,mod-2)%mod)%mod;
    printf("%d\n",ans);
    return 0;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code