CF2030E MEXimize the Score 题解

上 CM 了，纪念一下。

考虑从小到大对于每一种数字算贡献。

设 $f_{i,j}$ 表示有 $j$ 个 $a_x = i$ 对答案产生了 1 的贡献的方案数。那么显然有:

$f_{i,j} = \sum \limits_{k > j} f_{i-1,k}\cdot{cnt_i \choose j} + f_{i-1,j}\cdot \sum \limits_{k\geq j} {cnt_i \choose k}$

那么最后的答案就是 $\sum f_{i,j} \cdot j$。

乍一看这个柿子是 $O(n^2)$ 的对吧，但是实际上首先转移可以前缀和优化做到 $O(1)$，其次有效注意到第二维是有一个上界为 $\min \limits_{j\leq i} (cnt_j)$ 的，而 $\sum cnt_i = n$。那么这样子其实第二维的有效状态数就是 $O(n)$ 的了。直接写就完事了。

// Problem: E. MEXimize the Score
// URL: https://codeforces.com/contest/2030/problem/E
// Writer:WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')	
#define endl puts("")
const int MAX = 2e5 + 10;
const int mod = 998244353;

int cnt[MAX];
int f[MAX];
int pre2[MAX];

int preasd[MAX];
int inv123[MAX];
int F114[MAX];

int a[MAX];

int quickPower(int a,int b,int p){int base=a,ans=1;while(b){if(b&1)ans*=base,ans%=p;base*=base;base%=p;b>>=1;}return ans;}
 
int c2(int n, int m){
	if(m > n)	return 0;
	return preasd[n] * F114[m] % mod * F114[n-m] % mod;
}

void solve(){
	
	
	
	int n = read();
	pre2[0] = 1;
	for(int i = 1; i <= n; i++){
		pre2[i] = pre2[i - 1] * 2 % mod;
		a[i] = read();
		cnt[a[i]]++;
	}
	int premin = n;
	for(int i = 0; i <= n + 1; i++)	f[i] = 0;
	f[n] = 1;
	int ans = 0;
	int pree2 = n;
	for(int i = 0; i < n; i++){
		if(!cnt[i]){
			break;
		}
		int pre = 0;
		pree2 = pree2 - cnt[i];
		int pree3 = 0;
		for(int j = premin + 1; j <= cnt[i]; j++){
			pree3 = (pree3 + c2(cnt[i], j)) % mod;
		}
		for(int j = premin; j >= 1; j--){
			int prefj = f[j];
			f[j] = pre * c2(cnt[i], j) % mod;
			pree3 = (pree3 + c2(cnt[i], j)) % mod;
			f[j] = (f[j] + prefj * pree3 % mod) % mod;
			pre = (pre + prefj) % mod;
			// write(i), put(), write(j), put(), write(ans), put(), write(f[j]), put(), write(pree2), endl;	
			ans = (ans + f[j] * pre2[pree2] % mod * j  % mod) % mod;
		}
		premin = min(premin, cnt[i]);
	}
	for(int i = 0; i <= n; i++)	cnt[i] = 0;
	write(ans), endl;
}

signed main(){
	preasd[0] = F114[0] = 1;
	preasd[1] = inv123[1] = F114[1] = 1;
	for(int i = 2; i < MAX; i++){
		preasd[i] = 1ll * preasd[i - 1] * i % mod;
		inv123[i] = 1ll * inv123[mod % i] * (mod - mod / i) % mod;
		F114[i] = 1ll * F114[i - 1] * inv123[i] % mod;
	}
	int t = read();
	while(t--)	solve();
	return 0;
}