KotobukiTsumugi
KazamaRuri
·
·
题解
给一种我考场上的更为巧妙的做法。
前情
被 dadaaa 搬到模拟赛，耗尽浑身解数惊险战胜（其实是 T1 没能一眼切，先凹这题了）。
分析
首先转化题意，考虑我从草稿纸上搬下来的这张图：
图中表示每个元素的出现次数。
显然的，这个集合划分 mex 之和最大应该是：
1+4+5=10
如果从每个数对 mex 的贡献来说，贡献式子应该形如前缀最小值累加的形式：
3+2+2+2+1=10
欸 ~ 前缀最小值。那么我们有新的形式化题面了：
给定长度为 n 的序列 a，其约束了另一个长为 n 的序列 b，满足 b_i \in [0,a_i]，且 b_i=x 的概率为 \frac {a_i \choose x } {2^{a_i}}。求前缀最小值累加和的期望。保证 \sum a_i =n。
做到这一步很多人都能秒掉了。
当然原题肯定不是求概率和期望啦，而是每种方案的和，概率其实是方案数。
设 f_i 表示前缀最小值为 i 的累加和，g_i 为前缀最小值为 i 的方案数。默认滚动数组，记上一轮的值为 f'_i,g'_i，数的上界为 a,a'。
先说 g_i 怎么推：
- 如果上一轮最小值已经为 i，那么这一轮最小值还要为 i 的话，那只要让当前的数 \ge i 就好了吧,这样最小值就不会变了。对吧对吧，这部分方案数为：
(\, \sum^{a}_{k=i} {a \choose k} \, )\ \cdot\ g'_i
- 只剩下
钢琴陪我谈了一天最小值从 >i 到当前的数恰好变小成 i 的方案数了，也就是：
{a \choose i}\ \cdot\ (\, \sum^{a'}_{k=i+1} g'_k\, )
综上：
g_i=(\, \sum^{a}_{k=i} {a \choose k} \, )\ \cdot\ g'_i \ + \ {a \choose i}\ \cdot\ (\, \sum^{a'}_{k=i+1} g'_k\, )
$$$
f_i=(\, \sum^{a}_{k=i} {a \choose k} \, )\ \cdot\ f'_i \ + \ {a \choose i}\ \cdot\ (\, \sum^{a'}_{k=i+1} f'_k\, )\ +\ i \cdot g_i
$$$
（注意有没有带 $'$ 哦）
最后 $ans=f_0$。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+5,mod=998244353,maxn=1e6;
ll n,a[N],f[N],g[N],suff[N],sufg[N],sufc[N],fac[N],ifac[N];
ll qp(ll x,int y){ ll res=1; for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod; return res; }
inline ll C(int n,int m){ return n>m?0:fac[m]*ifac[n]%mod*ifac[m-n]%mod; }
void solve(){
scanf("%lld",&n);
for(int i=1,x;i<=n;i++)
scanf("%d",&x),a[x]++;
ll v=a[0];
for(int i=0;i<=v;i++)
f[i]=(g[i]=C(i,v))*i%mod;
for(int i=v;~i;i--)
suff[i]=(suff[i+1]+f[i])%mod,
sufg[i]=(sufg[i+1]+g[i])%mod;
for(int k=1;k<=n;k++){
v=min(v,a[k]),sufc[a[k]+1]=0;
for(int i=a[k];~i;i--)
sufc[i]=(sufc[i+1]+C(i,a[k]))%mod;
for(int i=0;i<=v;i++){
g[i]=(C(i,a[k])*sufg[i+1]%mod+g[i]*sufc[i]%mod)%mod,
f[i]=(C(i,a[k])*suff[i+1]%mod+f[i]*sufc[i]%mod+i*g[i]%mod)%mod;
}
suff[v+1]=sufg[v+1]=0;
for(int i=v;~i;i--)
suff[i]=(suff[i+1]+f[i])%mod,
sufg[i]=(sufg[i+1]+g[i])%mod;
for(int i=v+1;i<=a[k];i++)
f[i]=g[i]=sufc[i]=suff[i]=sufg[i]=0;
}
printf("%lld\n",f[0]);
for(int i=0;i<=n+1;i++)
f[i]=g[i]=suff[i]=sufg[i]=sufc[i]=a[i]=0;
}
int main(){
fac[0]=1;
for(int i=1;i<=maxn;i++)
fac[i]=fac[i-1]*i%mod;
ifac[maxn]=qp(fac[maxn],mod-2);
for(int i=maxn;i;i--)
ifac[i-1]=ifac[i]*i%mod;
int T; scanf("%d",&T);
while(T--) solve();
return 0;
}
```