TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3233
  • 题目
  • P3233金轮法王的龙象般若功却被老师逮个正着
    限制 : 时间限制 : 40000 MS   空间限制 : 262144 KB
    评测说明 : 2s,256MB
    问题描述

    同学们在教室传答案,一点也不方,因为已经传过很多次了;同学们在教室里传答案被逮到了,但问题不大,以前被逮到过很多次了。

    全班共有$n$个同学,每次参与传答案的同学都是$n$个同学的一个子集。一学期共$2^n$有次考试,每次考试参与传答案的同学都不完全相同。

    老师每次考试有一半的概率记录这次考试参与传答案的同学名单,也有一半的概率当做什么也没发生。到了期末,老师检查一下自己记下的名单,找出每次都参与了传答案的同学,作为这学期的“始作俑者”。特别的,如果老师一学期没有记录任何一次考试的传答案名单,则没有学生是“始作俑者”。

    老师对第$i$个学生的惩罚系数是正整数$a_i$。期末抓出始作俑者之后,算出始作俑者人数$x$和最大的惩罚系数$y$,对全班施加的惩罚量$z=xy$。特别的,如果没有学生是始作俑者,惩罚量为0。

    求期末惩罚量的期望$E(z)$。为了方便,输出$E(z)\mod{998244353}$,容易证明,$E(z)\times2^{2^n}$是个整数。

    输入格式

    第一行一个整数$n$,表示全班的人数。

    第二行$n$个整数$a_1,a_2,\dots,a_n$,是老师对每个学生的惩罚系数。

    输出格式

    输出一个整数,表示答案。

    样例输入 1

    2
    1 1

    样例输出 1

    6

    样例输入 2

    2
    5 13

    样例输出 2

    62

    样例输入 3

    4
    3 5 7 9

    样例输出 3

    6392

    样例输入 4

    10
    2 3 5 7 11 13 15 17 23 29

    样例输出 4

    516623512

    提示

    样例说明1

    先不妨假设第$1,2,3,4$场考试时,参与传答案的同学集合分别是$\emptyset,{1},{2},{1,2}$。

    • 始作俑者$=\emptyset$有很多种情况,但惩罚量为$0$。
    • 始作俑者$={1}$可以是记录了第$2$场考试,或者第$2,4$两场考试,总概率为$\frac18$;人数为$1$,最大惩罚系数为$1$,所以惩罚量为$1$。
    • 始作俑者$={2}$同上。
    • 始作俑者$={1,2}$必须是只记录第$4$场考试,概率为$\frac1{16}$;人数为$2$,最大惩罚系数为$1$,所以惩罚量为$2$。

    惩罚量期望$E(z)=\frac18\times1+\frac{1}8\times1+\frac1{16}\times2=\frac38$,所以答案是$\frac{3}8\times2=6$。

    样例说明2

    先不妨假设第$1,2,3,4$场考试时,参与传答案的同学集合分别是$\emptyset,{1},{2},{1,2}$。

    • 始作俑者$=\emptyset$有很多种情况,但惩罚量为$0$。
    • 始作俑者$={1}$的概率为$\frac{1}8$,惩罚量为$5$。
    • 始作俑者$={2}$的概率为$\frac{1}8$,惩罚量为$13$。
    • 始作俑者$={1,2}$的概率为$\frac1{16}$,惩罚量为$26$。

    惩罚量期望$E(z)=\frac{1}8\times5+\frac{1}8\times13+\frac1{16}\times26=\frac{31}8$,所以答案是$\frac{31}8\times2=62$。

    数据规模与约定

    对于10%的数据,\(n=2\)

    对于30%的数据,\(n\leq4\)

    对于60%的数据,\(n\leq16\)

    对于100%的数据, \(2\leq n\leq2^{12},\quad 1\leq a_i\leq2^{20}\)

    对于110%的数据, \(2\leq n\leq2^{20},\quad 0\leq a_i<998244353\)


    来源  感谢nodgd