题目

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+iSaib
那么答案就是:

r

e

t

=

S

A

(

1

)

S

P

(

S

)

ret=\sum_{S∈A}(-1)^{|S|}P(S)

ret=SA(1)SP(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);
}

版权声明:本文为Eric1561759334原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/Eric1561759334/article/details/114359097