[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;
}