#P18666. Master of Both III
Master of Both III
Master of Both III
陈教授既精通理论计算机科学,又擅长乒乓球。现在他正忙着打乒乓球,于是把下面这道算法题留给了你。
给定整数 。对于一个集合 ,用 表示通过若干次下列操作,把 的所有元素变成 所需的最小总代价:
- 选择任意子集 和一个位移 ,把所有选中的元素 同时替换为 。一次操作的代价为 。
只需考虑 。用集合记号写,此操作为
$$S\leftarrow (S\setminus T)\cup\{(x+y)\bmod n\mid x\in T\}.$$原题还用含重复元素的集合举例说明操作:当 、 时,选取 、,被选中的两个元素变成 ,而未被选中的那个 保留,因此操作后为 。这个例子仅解释如何移动选中的元素;下文要求计算的每个初始 都不含重复元素。
考虑所有满足 、不含重复元素的集合,计算各自的 。为避免输出过多,只需输出
$$\sum_{\varnothing\ne S\subseteq\{0,1,\ldots,n-1\}} f(S)\left(\sum_{v\in S}2^v\right)\pmod{998244353}.$$输入格式
第一行包含一个整数 ,。
第二行包含 个整数 ,其中每个数满足 ,分别表示各个位移的一次操作代价。
输出格式
输出一行一个整数,即上述总和对 取模后的结果。
样例输入 1
3
2 1 2
样例输出 1
45
样例输入 2
4
1919810 999999998 999999997 114114514
样例输出 2
152175989