#P18666. Master of Both III

    ID: 18002 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-逆向思考状压 DPDAG 动态规划SOS DP状态维度消除

Master of Both III

Master of Both III

陈教授既精通理论计算机科学,又擅长乒乓球。现在他正忙着打乒乓球,于是把下面这道算法题留给了你。

给定整数 nn。对于一个集合 SS,用 f(S)f(S) 表示通过若干次下列操作,把 SS 的所有元素变成 00 所需的最小总代价:

  • 选择任意子集 T⊆ST\subseteq S 和一个位移 yy,把所有选中的元素 xx 同时替换为 (x+y) mod n(x+y)\bmod n。一次操作的代价为 wyw_y。

只需考虑 0≤y<n0\le y<n。用集合记号写,此操作为

$$S\leftarrow (S\setminus T)\cup\{(x+y)\bmod n\mid x\in T\}.$$

原题还用含重复元素的集合举例说明操作:当 n=3n=3、S={0,1,1}S=\{0,1,1\} 时,选取 T={0,1}T=\{0,1\}、y=2y=2,被选中的两个元素变成 {2,0}\{2,0\},而未被选中的那个 11 保留,因此操作后为 {2,0,1}\{2,0,1\}。这个例子仅解释如何移动选中的元素;下文要求计算的每个初始 SS 都不含重复元素。

考虑所有满足 ∅≠S⊆{0,1,…,n−1}\varnothing\ne S\subseteq\{0,1,\ldots,n-1\}、不含重复元素的集合,计算各自的 f(S)f(S)。为避免输出过多,只需输出

$$\sum_{\varnothing\ne S\subseteq\{0,1,\ldots,n-1\}} f(S)\left(\sum_{v\in S}2^v\right)\pmod{998244353}.$$

输入格式

第一行包含一个整数 nn,1≤n≤221\le n\le22。

第二行包含 nn 个整数 w0,w1,…,wn−1w_0,w_1,\ldots,w_{n-1},其中每个数满足 1≤wi≤1091\le w_i\le10^9,分别表示各个位移的一次操作代价。

输出格式

输出一行一个整数,即上述总和对 998244353998244353 取模后的结果。

样例输入 1

3
2 1 2

样例输出 1

45

样例输入 2

4
1919810 999999998 999999997 114114514

样例输出 2

152175989