2023牛客OI赛前集训营-提高组（第二场） 集合

题目大意

给定正整数$n$，求有$n$个元素的集合 { 1 , 2 , … , n } \{1,2,\dots,n\} {1,2,…,n}的所有非空子集和的乘积模$998244353$后的结果。

$1\le n\le 200$

题解

依题意，非空子集和的取值范围为$[1,\frac{n\times (n+1)}{2}]$。

考虑$DP$。设$f_{i,j}$表示有$i$个元素的集合 { 1 , 2 , … , i } \{1,2,\dots,i\} {1,2,…,i}中非空子集和为$j$的子集数量。那么，可以用$O(n^3)$的时间复杂度求出$f_{i,j}$。

由扩展欧拉定理，可得在求$f_{i,j}$时模数为$\varphi (998244353)$，也就是$998244352$。

那么，答案为

$ans=\sum _{i=1}^{n\times (n+1)/2}{i}^{f_{n,i}}$

这个式子的模数为$998244353$。

于是，问题就解决了。

时间复杂度为$O(n^3)$。

code

#include
using namespace std;
const long long mod=998244353;
int n,l;
long long ans=1,f[205][40005];
long long mi(long long t,long long v){
	if(!v) return 1;
	long long re=mi(t,v/2);
	re=re*re%mod;
	if(v&1) re=re*t%mod;
	return re;
}
int main()
{
	scanf("%d",&n);
	l=n*(n+1)/2;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=l;j++){
			f[i][j]=f[i-1][j];
			if(j>=i) f[i][j]=(f[i][j]+f[i-1][j-i])%(mod-1);
		}
	}
	for(int i=1;i<=l;i++){
		ans=ans*mi(i,f[n][i])%mod;
	}
	printf("%lld",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29