题目
https://codeforces.com/gym/102978/problem/H
思路
做法和[PKUWC2018]猎人杀类似,且这题不需要多项式科技。
我们发现答案只与
b
b
b 的大小有关,而对于一个
b
b
b 不产生贡献的条件是在所有
A
A
A 删掉之后删。且由于期望的线性性,我们只需要考虑
M
=
1
M=1
M=1 的情况,然后把它们的贡献加起来就好。
然而我们发现这个东西并不好算,但是我们可以很容易算出
b
b
b 在所有
A
A
A 删掉之前删的概率:
b
b
+
∑
i
=
1
n
a
i
\frac{b}{b+\sum_{i=1}^{n}a_i}
b+∑i=1naib
考虑容斥,令
P
(
S
)
P(S)
P(S) 表示集合
S
S
S 在
b
b
b 之后删的概率。由于其他的
a
i
a_i
ai 对
S
S
S 没有影响,所以
P
(
S
)
P(S)
P(S) 的计算也是类似的:
b
b
+
∑
i
∈
S
a
i
\frac{b}{b+\sum_{i∈S}a_i}
b+∑i∈Saib
那么答案就是:
r
e
t
=
∑
S
∈
A
(
−
1
)
∣
S
∣
P
(
S
)
ret=\sum_{S∈A}(-1)^{|S|}P(S)
ret=S∈A∑(−1)∣S∣P(S)
然而我们不可能枚举所有子集。但是我们发现
∑
a
i
\sum a_i
∑ai 只有
10000
10000
10000
所以用的
D
P
DP
DP 分治FFT求一下系数就行啦
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+77,mod=998244353;
ll ans,a[N],f[N],g[N],b[N];
int n,m;
ll power(ll x,ll t)
{
ll b=1;
while(t)
{
if(t&1) b=b*x%mod; x=x*x%mod; t>>=1;
}
return b;
}
ll calc(ll sum)
{
ll yjy=0;
for(int i=1; i<=m; i++) (yjy+=b[i]*power((sum+b[i])%mod,mod-2)%mod)%=mod;
return yjy;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=1; i<=m; i++) scanf("%lld",&b[i]);
for(int i=0; i<=10000; i++) f[i]=calc(i);
g[0]=mod-1;
for(int i=1; i<=n; i++) for(int j=10000; j>=a[i]; j--) (g[j]+=g[j-a[i]]*(mod-1)%mod)%=mod;
ll ans=0;
for(int i=1; i<=10000; i++) (ans+=g[i]*f[i]%mod)%=mod;
printf("%lld",ans+n);
}