#1816. 最后的晚餐
最后的晚餐
最后的晚餐
题目描述
标题: 最后的晚餐 - Problem - QOJ.ac
#7976. 最后的晚餐
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