[LGP4707] 重返现世
2019-08-16 07:48:22来源:博客园 阅读 ()
[LGP4707] 重返现世
世界是物质的,物质是运动的,运动是有规律的,规律是可以被认识的。
关于期望意义下min-max容斥,我们认为每个事件的时间来认识事件,max/min S表示集合S中所有时间最后/最前出现的事件,E(max/min S)表示事件max/min S首次发生的期望时间。这样,仿照普通min-max容斥的推导可得
\[
E(\max S)=\sum_{T\subseteq S}(-1)^{|T|-1}E(\min T)
\]
同理的kth-max-min也成立
\[
E(\max_k S)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\min T)
\]
而对于\(E(\min S)\)我们有
\[
E(\min S)=\frac1{\sum_{e\in S}P(e)}\\
E(\max_k S)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\frac1{\sum_{e\in T}P(e)}
\]
赞美太阳,重返现世。
我们求的是收集到任意k种,所以
\[
E(\min_k S)=E(\max_{n-k+1} S)\\
k\Leftarrow n-k+1
\]
考虑由前\(i\)种时间构成的集合\(S_i\),计算其\(E(\max_k S_i)\)时记\(f[i,j,k]\)为满足\(T\in S_i, \sum_{e\in T}P(e)=j\)的系数和,即
\[
f[i,j,k]=\sum_{T\in S_i, \sum_{e\in T}P(x)=j} (-1)^{|T-k|}\binom{|T|-1}{k-1}
\]
显然最终答案
\[
E(\max_k)=\sum_{j}f[n,j,k]\times \frac1j
\]
由于题目规定\(P(x)=\frac{P_x}m\),则\(E(x)=\frac{m}{P_x}\),最后将\(m\)单独乘入即可。
再考虑dp的转移,决策是事件\(i\)的加入对系数的影响
\[
f[i,j,k]=\sum_{... i\not\in T} (-1)^{|T-k|}\binom{|T|-1}{k-1}+\sum_{... i\in T} (-1)^{|T-k|}\binom{|T|-1}{k-1}\\
=f[i-1,j,k]+\sum_{... i\in T} (-1)^{|T-k|}(\binom{|T|-2}{k-1}+\binom{|T|-2}{k-2})\\
=f[i-1,j,k]+\sum_{... i\in T} (-1)^{|T-k|}\binom{|T|-2}{k-1}+\sum_{... i\in T} (-1)^{|T-k|}\binom{|T|-2}{k-2}\\
=f[i-1,j,k]-f[i-1,j-P_i,k]+f[i-1,j-P_i,k-1]\\
\]
于是暴力做就行了。
#include <bits/stdc++.h>
#define IL inline
#define ll long long
using namespace std;
const int N=1e3+10;
const int M=1e4+10;
const int mod=998244353;
int n,K,m,p[N],s[N];
int ans,inv[M],f[2][M][12];
int main() {
scanf("%d%d%d",&n,&K,&m); K=n-K+1;
for(int i=1; i<=n; ++i) {
scanf("%d",p+i);
s[i]=s[i-1]+p[i];
}
f[0][0][0]=1;
for(int i=1; i<=n; ++i) {
memset(f[i&1],0,sizeof f[0]);
auto F=f[i&1],G=f[(i&1)^1];
F[0][0]=1;
for(int j=1; j<p[i]; ++j)
for(int k=1; k<=K; ++k)
F[j][k]=G[j][k];
for(int j=p[i]; j<=s[i]; ++j)
for(int k=1; k<=K; ++k)
F[j][k]=(G[j][k]+(mod-G[j-p[i]][k]+G[j-p[i]][k-1])%mod)%mod;
}
inv[1]=1;
for(int i=1; i<=m; ++i) {
if(i>1) inv[i]=(ll)inv[mod%i]*(mod-mod/i)%mod;
ans=(ans+(ll)f[n&1][i][K]*inv[i]%mod*m%mod)%mod;
}
printf("%d\n",ans);
return 0;
}
原文链接:https://www.cnblogs.com/nosta/p/11166927.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:bzoj3676 回文串
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash