QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
Statistics

对于由正整数构成的可重集合 $ A $,将其所有元素按照任意顺序排列得到序列 $ a=a_1,a_2,\cdots,a_n $。记长为 $ n+1 $ 的序列 $ b=b_0,b_1,\cdots,b_n $ 满足 $ \displaystyle b_i=\lfloor\frac{\sum_{j=1}^ia_j}{10}\rfloor $。记 $ \displaystyle f(A)=\max_{a}{|\{b\}|} $,其中 $ |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 $