#1816. 最后的晚餐

    ID: 1816 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1456来源:qoj.ac数据:公开样例枚举

最后的晚餐

最后的晚餐

题目描述

标题: 最后的晚餐 - 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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
1
2

样例 2

6
1 1 2 2 3 3
31