QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[+7]

# 7976. 最后的晚餐

Statistics

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

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

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

输入格式

第一行一个整数 n 表示集合 A 的大小,接下来一行 n 个整数 a_1,a_2,\cdots,a_n ,可重集合 S 即为 \{a_1,a_2,\cdots,a_n\}

输出格式

一行,表示答案对 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\le 2000, 1\le a_i\le 12

子任务编号 n\le 特殊性质子任务分值
1 20 4
2 40 12
3 2000 a_i\le 11 16
4 2000 a_i\ne1 12
5 100 12
6 300 8
7 600 12
8 2000 24