世界是物质的,物质是运动的,运动是有规律的,规律是可以被认识的。
关于期望意义下min-max容斥,我们认为每个事件的时间来认识事件,max/min s表示集合s中所有时间最后/最前出现的事件,e(max/min s)表示事件max/min s首次发生的期望时间。这样,仿照普通min-max容斥的推导可得
[ e(max s)=sum_{tsubseteq s}(-1)^{|t|-1}e(min t) ]
同理的kth-max-min也成立
[ e(max_k s)=sum_{tsubseteq s}(-1)^{|t|-k}binom{|t|-1}{k-1}e(min t) ]
而对于(e(min s))我们有
[ e(min s)=frac1{sum_{ein s}p(e)}\ e(max_k s)=sum_{tsubseteq s}(-1)^{|t|-k}binom{|t|-1}{k-1}frac1{sum_{ein t}p(e)} ]
赞美太阳,重返现世。
我们求的是收集到任意k种,所以
[ e(min_k s)=e(max_{n-k+1} s)\ kleftarrow n-k+1 ]
考虑由前(i)种时间构成的集合(s_i),计算其(e(max_k s_i))时记(f[i,j,k])为满足(tin s_i, sum_{ein t}p(e)=j)的系数和,即
[ f[i,j,k]=sum_{tin s_i, sum_{ein 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_{… inotin t} (-1)^{|t-k|}binom{|t|-1}{k-1}+sum_{… iin t} (-1)^{|t-k|}binom{|t|-1}{k-1}\ =f[i-1,j,k]+sum_{… iin t} (-1)^{|t-k|}(binom{|t|-2}{k-1}+binom{|t|-2}{k-2})\ =f[i-1,j,k]+sum_{… iin t} (-1)^{|t-k|}binom{|t|-2}{k-1}+sum_{… iin 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("%dn",ans); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602751.html