Problem:


Problem M: Power Subsequences

Problem

  添字が $1$ から始まり、長さが有限の数列を引数とする関数 $f$ を以下のように定義する。

  $\displaystyle f(\{a_1, a_2, \ldots, a_n\}) = \sum_{i=1}^n {a_i}^i$

  長さ $N$ の数列 $X = \{ x_1, x_2, \ldots, x_N \}$ が与えられるので、空の列を除く全ての部分列 $X'$ に対して $f(X')$ を求め、その総和を $998244353$ で割ったあまりを出力せよ。ただし、部分列の添字は、元の数列における相対的な序列を保ったまま $1$ から順に番号を振り直すものとする。また、ある2つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとする。

Input

入力は以下の形式で与えられる。

$N$
$x_1$ $\ldots$ $x_N$

1行目に長さ $N$ が与えられる。
2行目に数列 $X$ の要素が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

  
$1 \leq N \leq 10^6 $

  
$1 \leq x_i \leq 10^6 $

  
入力は全て整数である

Output

  空の列を除く全ての部分列 $X'$ について $f(X')$ を求め、その総和を $998244353$ で割ったあまりを出力せよ。

Sample Input 1

3
1 2 3

Sample Output 1

64

  $(1^1)+(2^1)+(1^1+2^2)+(3^1)+(1^1+3^2)+(2^1+3^2)+(1^1+2^2+3^3) = 64$

  であるから、64を出力する。

Sample Input 2

5
100 200 300 400 500

Sample Output 2

935740429



Sample input:
3
1 2 3


Sample output:
64

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353


def solve():
    n = I()
    x = LI()
    ans = 0
    for i in range(n):
        xi = x[i]
        ans += pow(2,n-i-1,mod)*xi*pow(xi+1,i,mod)
        if ans >= mod:
            ans %= mod
    print(ans)
    return


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int, input().split()))
ans = 0
mod = 998244353
for i, x in enumerate(X):
    ans = (ans * 2 + x * pow(x+1, i, mod)) % mod
print(ans)