#PQJ1456x7976. QOJ 1456_7976

    ID: 2613 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测枚举

QOJ 1456_7976

标题: 最后的晚餐 - Problem - QOJ.ac

#7976. 最后的晚餐

Statistics

The problem was used in the following contests:

对于由正整数构成的可重集合 A,将其所有元素按照任意顺序排列得到序列 a=a1,a2,⋯,an。记长为 n+1 的序列 b=b0,b1,⋯,bn 满足 bi=⌊∑j=1iaj10⌋。记 f(A)=maxa|{b}|,其中 |S| 表示不可重集合 S 的大小。即任选 a,求 b 中不同数的个数的最大值。特别地,有 f(∅)=1。

给定可重集合 A,对其 A 的所有本质不同的子集 B 求 f(B) 之和 mod998244353 的值。

称两个可重集合 X,Y 是本质不同的,当且仅当存在一个数 v,v 在 X,Y 中的出现次数不同。

输入格式

第一行一个整数 n 表示集合 A 的大小,接下来一行 n 个整数 a1,a2,⋯,an,可重集合 S 即为 {a1,a2,⋯,an}。

输出格式

一行,表示答案对 998244353 取模后的值。

样例一

input
1
1 
output
2

样例二

input
6
1 1 2 2 3 3  
output
31

样例三

input
12
1 2 3 4 5 6 7 8 9 10 11 12 
output
18228

数据范围与约束

对于所有数据,n≤2000,1≤ai≤12。

子任务编号n≤特殊性质子任务分值120无4240无1232000ai≤111642000ai≠1125100无126300无87600无1282000无24