专栏文章

KotobukiTsumugi

KKazamaRuri
CF2030E题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqf7519
此快照首次捕获于
2025/12/04 03:49
3 个月前
此快照最后确认于
2025/12/04 03:49
3 个月前
查看原文
给一种我考场上的更为巧妙的做法。

前情

被 dadaaa 搬到模拟赛，耗尽浑身解数惊险战胜（其实是 T1 没能一眼切，先凹这题了）。

分析

首先转化题意，考虑我从草稿纸上搬下来的这张图：
图中表示每个元素的出现次数。
显然的，这个集合划分 mex 之和最大应该是：
1+4+5=101+4+5=10
如果从每个数对 mex 的贡献来说，贡献式子应该形如前缀最小值累加的形式：
3+2+2+2+1=103+2+2+2+1=10
欸 ~ 前缀最小值。那么我们有新的形式化题面了：
给定长度为 nn 的序列 aa，其约束了另一个长为 nn 的序列 bb，满足 bi∈[0,ai]b_i \in [0,a_i]，且 bi=xb_i=x 的概率为 (aix)2ai\frac {a_i \choose x } {2^{a_i}}。求前缀最小值累加和的期望。保证 ∑ai=n\sum a_i =n。
做到这一步很多人都能秒掉了。
当然原题肯定不是求概率和期望啦，而是每种方案的和，概率其实是方案数。
设 fif_i 表示前缀最小值为 ii 的累加和，gig_i 为前缀最小值为 ii 的方案数。默认滚动数组，记上一轮的值为 fi′,gi′f'_i,g'_i，数的上界为 a,a′a,a'。
先说 gig_i 怎么推：
  1. 如果上一轮最小值已经为 ii，那么这一轮最小值还要为 ii 的话，那只要让当前的数 ≥i\ge i 就好了吧,这样最小值就不会变了。对吧对吧，这部分方案数为：
( ∑k=ia(ak) ) ⋅ gi′(\, \sum^{a}_{k=i} {a \choose k} \, )\ \cdot\ g'_i
  1. 只剩下钢琴陪我谈了一天最小值从 >i>i 到当前的数恰好变小成 ii 的方案数了，也就是：
(ai) ⋅ ( ∑k=i+1a′gk′ ){a \choose i}\ \cdot\ (\, \sum^{a'}_{k=i+1} g'_k\, )
综上：
gi=( ∑k=ia(ak) ) ⋅ gi′ + (ai) ⋅ ( ∑k=i+1a′gk′ )g_i=(\, \sum^{a}_{k=i} {a \choose k} \, )\ \cdot\ g'_i \ + \ {a \choose i}\ \cdot\ (\, \sum^{a'}_{k=i+1} g'_k\, )
ii 的对答案的贡献次数就是 gig_i，类似地，我们有:
fi=( ∑k=ia(ak) ) ⋅ fi′ + (ai) ⋅ ( ∑k=i+1a′fk′ ) + i⋅gif_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=f0ans=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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...