Problem:
 Score : 600 points    Problem Statement You are given N integers. The i -th integer is a_i .
Find the number, modulo 998244353 , of ways to paint each of the integers red, green or blue so that the following condition is satisfied:   Let R , G and B be the sums of the integers painted red, green and blue, respectively. There exists a triangle with positive area whose sides have lengths R , G and B .       Constraints  3 \leq N \leq 300  1 \leq a_i \leq 300(1\leq i\leq N)  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  a_1  :  a_N       Output Print the number, modulo 998244353 , of ways to paint each of the integers red, green or blue so that the condition is satisfied.        Sample Input 1 4
1
1
1
2      Sample Output 1 18  We can only paint the integers so that the lengths of the sides of the triangle will be 1 , 2 and 2 , and there are 18 such ways.       Sample Input 2 6
1
3
2
3
5
2      Sample Output 2 150       Sample Input 3 20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4      Sample Output 3 563038556

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
mod = 998244353
sm = sum(a)
dp = [[0 for i in range(sm+1)] for j in range(n+1)]
dp2 = [[0 for i in range(sm+1)] for j in range(n+1)]
dp[0][0] = 1
dp2[0][0] = 1
for i in range(1,n+1):
  x = a[i-1]
  dp2[i] = dp2[i-1][:]
  for j in range(sm+1):
    dp[i][j] = dp[i-1][j]*2
    if j >= x:
      dp[i][j] += dp[i-1][j-x]
      dp2[i][j] += dp2[i-1][j-x]
    dp[i][j] %= mod
    dp2[i][j] %= mod
ans = pow(3,n,mod)-sum(dp[-1][(sm+1)//2:])*3
if sm%2:
  print(ans%mod)
else:
  print((ans+dp2[-1][sm//2]*(mod+1)//2*6)%mod)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np

mod = 998244353
N = int(input())
A = [int(input()) for _ in range(N)]

L = sum(A)//2
dp1 = np.zeros((L+1,), dtype=int)
dp2 = np.zeros((L+1,), dtype=int)
dp1[0] = 1
dp2[0] = 1
for a in A:
    if a >= L+1: continue
    dp1 = (dp1 + np.concatenate((np.zeros((a,), dtype=int), dp1[:L+1-a]))) % mod
    dp2 = (dp2 + np.concatenate((np.zeros((a,), dtype=int), 2*dp2[:L+1-a]))) % mod

p1 = 0
p2 = 0
for s in range(1,L+1):
    p1 = (p1 + dp1[s]*6)%mod
    p2 = (p2 + dp2[s]*3)%mod
ans = (pow(3, N, mod) + 3 - 3*pow(2, N, mod) - p2 + p1) % mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


mod = 998244353
N = int(input())
A = [int(input()) for _ in range(N)]

S = sum(A)
L = S//2
dp1 = [0]*(L+1)
dp2 = [0]*(L+1)
dp1[0] = 1
dp2[0] = 1
for a in A:
    for i in reversed(range(L-a+1)):
        dp1[i+a] = (dp1[i+a] + dp1[i])%mod
        dp2[i+a] = (dp2[i+a] + dp2[i]*2)%mod

p1 = 0
p2 = 0
for s in range(1,L+1):
    p1 = (p1 + dp1[s]*6)%mod
    p2 = (p2 + dp2[s]*3)%mod
ans = (pow(3, N, mod) + 3 - 3*pow(2, N, mod) - p2 + p1) % mod
print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
sum_a = sum(a)
MOD = 998244353

dp = [0] * (sum_a + 1)
dp[0] = 1
for i in range(n):
    for j in range(sum_a + 1)[::-1]:
        
        dp[j] += dp[j]
        if j - a[i] >= 0:
            dp[j] += dp[j - a[i]]
        dp[j] %= MOD
        
dq = [0] * (sum_a + 1)
dq[0] = 1
for i in range(n):
    for j in range(sum_a + 1)[::-1]:
        
        if j - a[i] >= 0:
            dq[j] += dq[j - a[i]]
            dq[j] %= MOD
        else:
            break

ans = 0
for j in range(sum_a + 1):
    if sum_a <= j * 2:
        ans += dp[j] * 3
        ans %= MOD

if sum_a % 2 == 0:
    ans -= dq[sum_a // 2] * 3

print((3 ** n - ans) % MOD)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
sum_a = sum(a)
MOD = 998244353

dp = [[0] * (sum_a + 1) for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(sum_a + 1):
        
        if j - a[i] >= 0:
            dp[i + 1][j] += dp[i][j - a[i]]
        
        dp[i + 1][j] += dp[i][j] * 2
        dp[i + 1][j] %= MOD
        
dq = [[0] * (sum_a + 1) for i in range(n + 1)]
dq[0][0] = 1
for i in range(n):
    for j in range(sum_a + 1):
        
        if j - a[i] >= 0:
            dq[i + 1][j] += dq[i][j - a[i]]
        
        dq[i + 1][j] += dq[i][j]
        dq[i + 1][j] %= MOD

ans = 0
for j in range(sum_a + 1):
    if sum_a <= j * 2:
        ans += dp[-1][j] * 3
        ans %= MOD

if sum_a % 2 == 0:
    ans -= dq[-1][sum_a // 2] * 3

print((3 ** n - ans) % MOD)

Solution (Python):
N = int(input())
P = 998244353
A = [int(input()) for _ in range(N)]
s = sum(A)

def calc(m):
    X = [1] + [0] * s
    for a in A:
        for i in range(a, s+1)[::-1]:
            X[i] = (X[i] + X[i-a] * m) % P
    return X

Y = calc(2)
ans = sum([Y[i] for i in range(s//2+1)]) + (0 if s%2 else -calc(1)[s//2])
print((pow(3, N, P) - ans*3) % P)

Solution (Python):
mod=998244353 

N=int(input())
alist=[]
all_num=1
for i in range(N):
  alist.append(int(input()))
  all_num *= 3
  all_num %= mod
  
asum=sum(alist)



dp=[]
dp2=[]
for _ in range(N+1):
  dp.append([0]*(asum+1))
  dp2.append([0]*(asum+1))
  
dp[0][0]=1
dp2[0][0]=1

for i in range(N):
  a=alist[i]
  for j in range(asum):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    dp2[i+1][j] += dp2[i][j]
    dp2[i+1][j] %= mod
    if dp[i][j] > 0:
      dp[i+1][j+a] += dp[i][j]
      dp[i+1][j+a] %= mod
      dp2[i+1][j+a] += dp2[i][j]
      dp2[i+1][j+a] %= mod
    



invalid_num = sum(dp[N][(asum+1)//2:])%mod 


if asum%2 == 0:
  print((all_num-3*invalid_num+3*dp2[N][asum//2])%mod)
else:
  print((all_num-3*invalid_num)%mod)

Solution (Python):
MOD = 998244353
def pow(n,k,m):
    ans = 1
    while k>0:
        if(k & 1):ans = (ans*n) % m
        n = (n*n)%m
        k >>= 1
    return ans

n = int(input())
a =[int(input()) for i in range(n)]
s = sum(a)
dp1 = [0 for i in range(s+1)] 

dp1[0] = 1

for i in  a:
    dpp1 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+i <= s:dpp1[j+i] = (dp1[j]+dpp1[j+i]) % MOD
        dpp1[j] = (dp1[j]*2 + dpp1[j]) % MOD
    dp1 = dpp1[:]

if s % 2 == 1:
    ans1 = sum(dp1[(s//2) + 1:]) % MOD
    print((pow(3,n,MOD)-ans1*3) % MOD)
    exit()

ans1 = sum(dp1[(s//2):]) % MOD

dp2 = [0 for i in range(s+1)]

dp2[0] = 1

for i in a:
    dpp2 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+i <= s:dpp2[j+i] = (dp2[j]+dpp2[j+i]) % MOD
        dpp2[j] = (dp2[j] + dpp2[j]) % MOD
    dp2 = dpp2[:]

print((pow(3,n,MOD)-(ans1*3 - dp2[s//2]*3)) % MOD)

Solution (Python):
import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
MOD = 998244353
N = ni()
a = np.array([int(input()) for i in range(N)])
sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1), dtype=np.int64)
dp[0,0] = 1
 
for i in range(1, N+1):
    
    a_i = a[i-1]
    dp[i,a_i:] += dp[i-1,:-a_i]
    
    
    dp[i,:] += dp[i-1,:]*2
    dp[i,:] %= MOD

ex = np.sum(dp[N,(sum_a+1)//2:])%MOD

res = 3**N%MOD -ex*3

if sum_a%2 == 0:
    dp = np.zeros((N+1, sum_a+1), dtype=np.int64)
    dp[0,0] = 1
    for i in range(1, N+1):
        a_i = a[i-1]
        dp[i,a_i:] += dp[i-1,:-a_i]
        dp[i,:] += dp[i-1,:]
        dp[i,:] %= MOD
    res += dp[N, sum_a//2] * 3
print(res%MOD)

Solution (Python):
import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]

modulo = 998244353

a.sort(reverse=True)
cumsump1 = 1
s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    cumsump1 += ai
    dp[ai:cumsump1] = 2 * dp[ai:cumsump1] + dp[: -ai + cumsump1]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo

ans = 3 ** n % modulo
ans -= 3 * dp[ceil(s / 2) :].sum()

if s % 2 == 0:
    dp = np.zeros(s // 2 + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] = (dp[ai:] + dp[:-ai]) % modulo

    ans += 3 * dp[s // 2]

ans %= modulo

print(ans)

Solution (Python):
import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    dp[ai:] = 2 * dp[ai:] + dp[:-ai]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo

sol = 3 ** n % modulo
sol -= 3 * dp[ceil(s / 2) :].sum()

if s % 2 == 0:
    dp = np.zeros(s // 2 + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] = (dp[ai:] + dp[:-ai]) % modulo

    sol += 3 * dp[s // 2]

sol %= modulo

print(sol)

Solution (Python):
import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    dp[ai:] = 2 * dp[ai:] + dp[:-ai]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo
sol = 3 ** n % modulo
sol -= 3 * dp[ceil(s / 2) :].sum()


if s % 2 == 0:
    dp = np.zeros(s + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] = dp[ai:] + dp[:-ai]
        dp %= modulo

    sol += 3 * dp[s // 2]

sol %= modulo

print(sol)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = [ni() for _ in range(n)]

suma = sum(a)
MOD = 998244353

dp_rgb = [[0]*(suma+1) for _ in range(n+1)]
dp_gb = [[0]*(suma+1) for _ in range(n+1)]

dp_rgb[0][0] = 1
dp_gb[0][0] = 1

for i, ai in enumerate(a):
    for sm in range(suma+1):
        if sm + ai <= suma:
            dp_rgb[i+1][sm+ai] += dp_rgb[i][sm] % MOD
            dp_gb[i+1][sm+ai] += dp_gb[i][sm] % MOD
            
        dp_rgb[i+1][sm] += 2 * dp_rgb[i][sm] % MOD
        dp_gb[i+1][sm] += dp_gb[i][sm] % MOD
        
ng = 3 * sum(dp_rgb[n][-(-suma//2):]) % MOD
ok = 0 if suma%2 else 3*dp_gb[n][suma//2] % MOD

print((pow(3,n,MOD) - ng + ok) % MOD)

Solution (Python):
import numpy as np

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)

dp = np.zeros((N,suma+1,2),dtype = np.int)
dp[0,0,0] = 2
dp[0,a[0],0] = 1
dp[0,0,1] = 1
dp[0,a[0],1] = 1

allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	dp[i,k:,0] += dp[i-1,:-k,0]
	dp[i,:,0] += dp[i-1,:,0]*2
	dp[i,k:,1] += dp[i-1,:-k,1]
	dp[i,:,1] += dp[i-1,:,1]
	if(i%10 == 0):
		dp[i,:,:] = dp[i,:,:]%DIV
allc = allc - sum(dp[N-1,suma-suma/2:,0])*3
if(suma % 2 == 0):			
	allc += dp[N-1,suma/2,1]*3
print(int(allc%DIV))

Solution (Python):
import math
import copy
import numpy as np

MOD = 998244353

n = int(input())
xxs = []
total = 0
for _ in range(n):
    t = int(input())
    xxs.append(t)
    total += t

xs = np.array(xxs)
dp = np.array([[0] * (total+1) for _ in range(n)])

dp[0][0] = 2
dp[0][xs[0]] = 1

curtotal = xs[0]
for i in range(1,n): 
    s = xs[i]
    curtotal += s
    dp[i] = (dp[i-1] * 2)
    dp[i][s:] += dp[i-1][:-s]
    dp[i] %= MOD



plus = 0
if total % 2 == 0:
    dp2 = np.array([0] * (total // 2 + 1))
    dp2[0] = 1
    curtotal = 0
    for i in range(n):
        s = xs[i]
        curtotal += s
        prev = copy.copy(dp2)
        dp2[s:] += prev[:-s]
        dp2 %= MOD
    plus = dp2[total//2]


minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD



print(((3**n)%MOD - minus*3 + plus*3) % MOD)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
suma = sum(a)
suma2 = suma // 2
mod = 998244353

dp1 = [3] + [0] * suma2
dp2 = [3] + [0] * suma2
for ai in a:
    for j in range(suma2, ai - 1, -1):
        dp1[j] = (dp1[j] + dp1[j - ai] * 2) % mod
        dp2[j] = (dp2[j] + dp2[j - ai]    ) % mod
half = dp2[suma2] if suma % 2 == 0 else 0
print(((3 ** n) - sum(dp1) + half + mod) % mod)

Solution (Python):
from collections import defaultdict

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

DP = [[0]*(S+1) for _ in range(2)]
DP[0][0] = 2
DP[0][A[0]] = 1


DP2 = [[0]*(S+1) for _ in range(2)]
DP2[0][0] = 1
DP2[0][A[0]] = 1


max_A = A[0]
for i in range(1, N):
    a = A[i]
    max_A += a
    curr_dp = DP[i % 2]
    prev_dp = DP[(i+1) % 2]
    curr_dp2 = DP2[i % 2]
    prev_dp2 = DP2[(i+1) % 2]
    for r in range(max_A+1):
        if r >= a:
            curr_dp[r] = prev_dp[r]*2 + prev_dp[r-a]
            curr_dp2[r] = prev_dp2[r] + prev_dp2[r-a]
        else:
            curr_dp[r] = prev_dp[r]*2
            curr_dp2[r] = prev_dp2[r]
        curr_dp[r] %= 998244353
        curr_dp2[r] %= 998244353



half_S = (S+1)//2
ans = pow(3, N, 998244353)
ans -= 3*sum(DP[(N-1) % 2][half_S:])
if S % 2 == 0:
    ans += 3*DP2[(N-1) % 2][S//2]

print(ans % 998244353)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j] += dp[i][j] * 2
		dp[i+1][j] %= MOD
		if j+a[i] <= s:
			dp[i+1][j+a[i]] += dp[i][j]
			dp[i+1][j+a[i]] %= MOD

res = 0
for j in range(s+1):
	if j*2 >= s:
		res += dp[n][j] * 3
		res %= MOD

if s%2 == 0:
	dpp = [0 for _ in range(s+1)]
	dpp[0] = 1
	for i in range(n):
		for j in range(s-a[i], -1, -1):
			dpp[j+a[i]] += dpp[j]
			dpp[j+a[i]] %= MOD
	res -= dpp[s//2] * 3

print((pow(3, n, MOD) - res) % MOD)

Solution (Python):

def dp_table(*counts):  
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    

    
    dp[0][A[0]] = 1
    dp[0][0] = 2  

    
    dp2 = [[0] * (sum_A+1) for i in range(N)]  
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  

    
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    
    
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np

n = int(sys.stdin.readline())
ms = []
for i in range(n):
    ms += [int(sys.stdin.readline())]

total = sum(ms)
dp = np.zeros(total + 1, dtype=np.int64)
dp[0] = 1

for m in ms:
    dp[m:] = (dp[m:] * 2 + dp[:-m]) % 998244353
    dp[:m] = dp[:m] * 2 % 998244353

border = (total + 1) // 2
yo = sum(dp[border:]) % 998244353 * 3

if total % 2 == 0:
    dp2 = np.zeros(total // 2 + 1, dtype=np.int64)
    dp2[0] = 1
    for m in ms:
        dp2[m:] = (dp2[m:] + dp2[:-m]) % 998244353
    yo = yo - dp2[-1] * 3 % 998244353

print((3 ** n  - yo)% 998244353)

Solution (Python):
import numpy as np

mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
S = sum(A)


D1 = np.zeros((N+1, S+1), dtype=int)
D1[0][0] = 1

D2 = np.zeros((N+1, S+1), dtype=int)
D2[0][0] = 1

for i in range(N):
    D1[i+1] += D1[i] * 2
    D1[i+1][A[i]:] += D1[i][:-A[i]]
    D1[i+1] = D1[i+1] % mod

    D2[i+1] += D2[i]
    D2[i+1][A[i]:] += D2[i][:-A[i]]
    D2[i+1] = D2[i+1] % mod

border = (S + 1) // 2

result = 3 ** N - 3 * sum(D1[N][border:]) + (border * 2 == S) * 3 * D2[N][border]

print(result % mod)

Solution (Python):
import numpy as np

mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
S = sum(A)


def fastpow(a, n):
    i = 0
    result = 1
    pow = [a]
    while (1 << i) <= n:
        pow.append(pow[-1] * pow[-1] % mod)
        i += 1
    for j in range(i):
        if (n >> j) % 2 == 1:
            result = result * pow[j] % mod
    return result


D1 = np.zeros((N+1, S+1), dtype=int)
D1[0][0] = 1

D2 = np.zeros((N+1, S+1), dtype=int)
D2[0][0] = 1

for i in range(N):
    D1[i+1] += D1[i] * 2
    D1[i+1][A[i]:] += D1[i][:-A[i]]
    D1[i+1] = D1[i+1] % mod

    D2[i+1] += D2[i]
    D2[i+1][A[i]:] += D2[i][:-A[i]]
    D2[i+1] = D2[i+1] % mod

border = (S + 1) // 2

result = fastpow(3, N)
result -= 3 * sum(D1[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print(result % mod)

Solution (Python):
import numpy as np

mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
S = sum(A)


def fastpow(a, n):
    i = 0
    result = 1
    pow = [a]
    while (1 << i) <= n:
        pow.append(pow[-1] * pow[-1] % mod)
        i += 1
    for j in range(i):
        if (n >> j) % 2 == 1:
            result = result * pow[j] % mod
    return result


D1 = np.zeros((N+1, S+1), dtype=int)
D1[0][0] = 1

D2 = np.zeros((N+1, S+1), dtype=int)
D2[0][0] = 1

for i in range(N):
    D1[i+1] += D1[i] * 2
    D1[i+1][A[i]:] += D1[i][:-A[i]]
    D1[i+1] = D1[i+1] % mod

    D2[i+1] += D2[i]
    D2[i+1][A[i]:] += D2[i][:-A[i]]
    D2[i+1] = D2[i+1] % mod

border = (S + 1) // 2

result = fastpow(3, N)
result -= 3 * sum(D1[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print(result % mod)

Solution (Python):
import numpy as np

mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
S = sum(A)










PS = [0 for i in range(N+1)]
for i in range(N):
    PS[i+1] = PS[i] + A[i]


D1 = np.zeros((N+1, S+1), dtype=int)
D1[0][0] = 1

D2 = np.zeros((N+1, S+1), dtype=int)
D2[0][0] = 1

for i in range(N):
    D1[i+1] += D1[i] * 2
    D1[i+1][A[i]:] += D1[i][:-A[i]]
    D1[i+1] = D1[i+1] % mod

    D2[i+1] += D2[i]
    D2[i+1][A[i]:] += D2[i][:-A[i]]
    D2[i+1] = D2[i+1] % mod

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D1[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print(result % mod)

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
A=[int(input()) for i in range(N)]
SUM=sum(A)
MAX=(SUM-1)//2

mod=998244353

DPLIST=[0]*(MAX+2)
DPLIST[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        if i==MAX+1:
            DPLIST[i]=DPLIST[i]*3%mod
        else:
            DPLIST[min(i+a,MAX+1)]=(DPLIST[min(i+a,MAX+1)]+DPLIST[i])%mod
            DPLIST[i]=DPLIST[i]*2%mod

if SUM%2==1:
    print((sum(DPLIST)-DPLIST[-1]*3)%mod)
    sys.exit()

MAX=SUM//2
       
DPLIST2=[0]*(MAX+2)
DPLIST2[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        DPLIST2[min(i+a,MAX+1)]=(DPLIST2[min(i+a,MAX+1)]+DPLIST2[i])%mod

        
print((sum(DPLIST)-DPLIST[-1]*3+DPLIST2[-2]*3)%mod)

Solution (Python):
import sys
import numpy as np

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

s = sum(aaa)
dp1 = np.zeros(s + 1, dtype=np.uint32)
dp2 = np.zeros(s + 1, dtype=np.uint32)
dp1[0] = 1
dp2[0] = 1
for a in aaa:
    dp1 = (dp1 * 2 + np.roll(dp1, a)) % MOD
    dp2 = (dp2 + np.roll(dp2, a)) % MOD

h = (s + 1) // 2
ans = (pow(3, n, MOD) - dp1[h:].sum() * 3) % MOD
if s % 2 == 0:
    ans = (ans + dp2[h] * 3) % MOD
print(int(ans))

Solution (Python):
import sys
import numpy as np

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

s = sum(aaa)
dp1 = np.zeros(s + 1, dtype=np.int64)
dp2 = np.zeros(s + 1, dtype=np.int64)
dp1[0] = 1
dp2[0] = 1
for a in aaa:
    dp1 = (dp1 * 2 + np.roll(dp1, a)) % MOD
    dp2 = (dp2 + np.roll(dp2, a)) % MOD

h = (s + 1) // 2
ans = (pow(3, n, MOD) - dp1[h:].sum() * 3) % MOD
if s % 2 == 0:
    ans = (ans + dp2[h] * 3) % MOD
print(ans)

Solution (Python):
import sys
import numpy as np

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

s = sum(aaa)
dp1 = np.zeros(s + 1, dtype=np.int64)
dp2 = np.zeros(s + 1, dtype=np.int64)
dp1[0] = 1
dp2[0] = 1
for a in aaa:
    dp1a = np.roll(dp1, a)
    dp1 *= 2
    dp1 %= MOD
    dp1 += dp1a
    dp1 %= MOD

    dp2 += np.roll(dp2, a)
    dp2 %= MOD

h = (s + 1) // 2
ans = (pow(3, n, MOD) - dp1[h:].sum() * 3) % MOD
if s % 2 == 0:
    ans = (ans + dp2[h] * 3) % MOD
print(ans)

Solution (Python):
import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)],dtype=np.int64)

TOTAL=pow(3,N,MOD)
ASum=np.sum(A)


dp=np.zeros((2,ASum+1),dtype=np.int64)
dp[0][0] = 2
dp[0][A[0]] = 1


dpOther=np.zeros((2,ASum+1),dtype=np.int64)
dpOther[0][0] = 1
dpOther[0][A[0]] = 1

prev=0
current=1
curMax=A[0]

for n, a in enumerate(A):
	if n==0:
		continue
	
	current = n % 2
	prev = (n+1) % 2
	
	dp[current,:] = dp[prev,:]*2 % MOD
	dp[current,a:] += dp[prev,:-a] % MOD

	if ASum %2 == 0:
		dpOther[current,:] = dpOther[prev,:] % MOD
		dpOther[current,a:] += dpOther[prev,:-a] % MOD

sumStart = 0
plus = 0

if ASum % 2 == 0:
	
	sumStart=ASum//2
	plus = (dpOther[current][ASum//2]*3) % MOD
else:
	
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )

Solution (Python):
import numpy as np

MOD=998244353
N=int(input())
A=np.array(sorted([int(input()) for _ in range(N)]))

TOTAL=pow(3,N,MOD)
ASum=np.sum(A)


dp=np.zeros((2,ASum+1),dtype=np.int64)
dp[0][0] = 2
dp[0][A[0]] = 1


dpOther=np.zeros((2,ASum+1),dtype=np.int64)
dpOther[0][0] = 1
dpOther[0][A[0]] = 1

prev=0
current=1
curMax=A[0]

for n, a in enumerate(A):
	if n==0:
		continue
	
	current = n % 2
	prev = (n+1) % 2
	
	dp[current,:] = dp[prev,:]*2 % MOD
	dp[current,a:] += dp[prev,:-a] % MOD

	if ASum %2 == 0:
		dpOther[current,:] = dpOther[prev,:] % MOD
		dpOther[current,a:] += dpOther[prev,:-a] % MOD

sumStart = 0
plus = 0

if ASum % 2 == 0:
	
	sumStart=ASum//2
	plus = (dpOther[current][ASum//2]*3) % MOD
else:
	
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )

Solution (Python):
import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)])

TOTAL=pow(3,N,MOD)
ASum=np.sum(A)


dp=np.zeros((2,ASum+1),dtype=np.int64)
dp[0][0] = 2
dp[0][A[0]] = 1


dpOther=np.zeros((2,ASum+1),dtype=np.int64)
dpOther[0][0] = 1
dpOther[0][A[0]] = 1

prev=0
current=1
curMax=A[0]

for n, a in enumerate(A):
	if n==0:
		continue
	
	current = n % 2
	prev = (n+1) % 2
	
	dp[current,:] = dp[prev,:]*2 % MOD
	dp[current,a:] += dp[prev,:-a]

	if ASum %2 == 0:
		dpOther[current,:] = dpOther[prev,:] % MOD
		dpOther[current,a:] += dpOther[prev,:-a]

sumStart = 0
plus = 0

if ASum % 2 == 0:
	
	sumStart=ASum//2
	plus = (dpOther[current][ASum//2]*3) % MOD
else:
	
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )

Solution (Python):
M,s=998244353,0
d=[1]+[0]*7**6
e=d[:]
for _ in'_'*input():
 a=input();s+=a;i=s
 while~i:d[i]+=d[i-a]*2%M;e[i]+=e[i-a]%M;i-=1
print(sum(d)+~s%2*e[s/2]*3-3*sum(d[:s/2+1]))%M

Solution (Python):
M,s=998244353,0
d=[1]+[0]*7**6
e=d[:]
n=input()
for _ in'_'*n:
 a=input();s+=a;i=s
 while~i:d[i]+=d[i-a]*2%M;e[i]+=e[i-a]%M;i-=1
print(3**n+~s%2*e[s/2]*3-3*sum(d[:s/2+1]))%M

Solution (Python):
Q = 998244353
N = int( input())
A = [ int( input()) for _ in range(N)]
S = sum(A)
H = (S+1)//2
dp = [0]*(S+1)
dp[0] = 1
for a in A:
    for s in range(S, a-1, -1):
        dp[s] = (dp[s]*2 + dp[s-a])%Q
    for s in range(a-1,-1,-1):
        dp[s] = dp[s]*2%Q
ans = (pow(3, N, Q) - sum(dp[H:])%Q*3%Q)%Q
if S%2 == 0:
    dp = [0]*(S+1)
    dp[0] = 1
    for a in A:
        for s in range(S,a-1,-1):
            dp[s] = (dp[s] + dp[s-a])%Q
    ans += dp[H]*3
    ans %= Q
print(ans)

Solution (Python):
Q = 998244353
N = int( input())
A = [ int( input()) for _ in range(N)]
S = sum(A)
H = (S+1)//2
dp = [0]*(S+1)
dp[0] = 1
for a in A:
    for s in range(S, a-1, -1):
        dp[s] = (dp[s]*2 + dp[s-a])%Q
    for s in range(a-1,-1,-1):
        dp[s] = dp[s]*2%Q
ans = (pow(3, N, Q) - sum(dp[H:])%Q*3%Q)%Q
if S%2 == 0:
    dp = [0]*(S+1)
    dp[0] = 1
    for a in A:
        for s in range(S,a-1,-1):
            dp[s] = (dp[s] + dp[s-a])%Q
    ans += dp[H]*3
    ans %= Q
print(ans)

Solution (Python):
M,s=998244353,0
d=[1]+[0]*7**6
e=d[:]
n=input()
for _ in'_'*n:
 a=input();s+=a;i=s
 while~i:d[i]+=d[i-a]*2%M;e[i]+=e[i-a]%M;i-=1
print(3**n+~s%2*e[s//2]*3-3*sum(d[:s//2+1]))%M

Solution (Python):
import numpy as np

N = int(input())
a = sorted([int(input()) for _ in range(N)])

s = sum(a)
m = (s + 1) // 2
m1 = m + 1


def func():
    ab = np.zeros(m1, dtype='uint32')
    ab[m] = 1
    for i in range(N):
        c = a[i]
        ab[:-c] = (2 * ab[:-c] + ab[c:]) % 998244353
        ab[-c:] = (2 * ab[-c:] + ab[m]) % 998244353
    return ab[0]


def func1():
    ab = np.zeros(m1, dtype='uint32')
    ab[m] = 1
    for i in range(N):
        c = a[i]
        ab[:-c] = (ab[:-c] + ab[c:]) % 998244353
        ab[-c:] = ab[-c:]
    return ab[0]


ans = 3 ** N % 998244353 - 3 * func()
if s % 2 == 0:
     ans += 3 * func1()
print(ans % 998244353)

Solution (Python):
N = int(input())
a = [int(input()) for _ in range(N)]
s = sum(a)
m = (s + 1) // 2

c1 = [0] * (m + 1)
c1[m] = 1
for i in range(N):
    d = a[i]
    for j in range(m - d + 1):
        c1[j] = (2 * c1[j] + c1[j + d]) % 998244353
    for j in range(m - d + 1, m + 1):
        c1[j] = (2 * c1[j] + c1[m]) % 998244353

ans1 = c1[0]

if s % 2:
    c1[0] = 0
else:
    for j in range(m):
        c1[j] = 0
    c1[m] = 1
    for i in range(N):
        d = a[i]
        for j in range(m - d + 1):
            c1[j] = (c1[j] + c1[j + d]) % 998244353
        for j in range(m - d + 1, m + 1):
            c1[j] = c1[j]

ans = (3 ** N % 998244353 - 3 * ans1 + 3 * c1[0]) % 998244353
print(ans)

Solution (Python):
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


import sys

input = sys.stdin.readline

N = int(input())
a = [int(input()) for _ in range(N)]
total = sum(a)
MOD = 998244353

'''(1)全体'''
U = pow(3, N, MOD)  

'''(2)単円'''
dp = [[0] * (total + 1) for _ in range(N + 1)]
dp[0][0] = 1


for i in range(N):
    for r in range(total + 1):
        if r - a[i] >= 0:
            dp[i + 1][r] += dp[i][r - a[i]]
        dp[i + 1][r] += 2 * dp[i][r]
        dp[i + 1][r] %= MOD
        


single_circle = 0
for r in range(total + 1):
    if r >= (total / 2):
        single_circle += dp[N][r]


'''(3)２円の積集合'''
if total % 2 == 0:
    dp2 = [[0] * (total + 1) for _ in range(N + 1)]
    dp2[0][0] = 1
    

    for i in range(N):
        for r in range(int(total / 2) + 1):
            if r - a[i] >= 0:
                dp2[i + 1][r] += dp2[i][r - a[i]]
            dp2[i + 1][r] += dp2[i][r]
            dp2[i + 1][r] %= MOD
    

two_circle_intersect = dp2[N][int(total / 2)] if total % 2 == 0 else 0

'''(3)３円の積集合'''
three_circle_intersect = 0

'''(4)解答'''
ans = 0

ans += U
ans %= MOD

ans -= 3 * single_circle
ans %= MOD

ans += 3 * two_circle_intersect
ans %= MOD

ans -= three_circle_intersect
ans %= MOD

print(ans)

Solution (Python):

"""
Created on Sun Apr 21 18:51:07 2019

@author: Yamazaki Kenichi
"""

N = int(input())
A = [int(input()) for i in range(N)]
mod = 998244353
def mof(x):
    return x % mod
total = sum(A)
dp1 = [[0 for i in range(300*N+1)] for i in range(N+1)]
dp2 = [[0 for i in range(300*N+1)] for i in range(N+1)]
dp1[0][0], dp2[0][0] = 1,1
for i in range(N):
    for j in range(N*300+1):
        dp1[i+1][j] = mof(dp1[i][j]*2 + (dp1[i][j-A[i]] if j >= A[i] else 0))
        dp2[i+1][j] = mof(dp2[i][j] + (dp2[i][j-A[i]] if j >= A[i] else 0))
        
ex = mof(sum(dp1[N][(total+1)//2:]))
a = dp2[N][total//2] if total % 2 == 0 else 0

ans = mof(3**N - 3*ex + 3*a)
print(ans)

Solution (Python):
M,s=998244353,0
d=[1]+[0]*7**6
e=d[:]
n=input()
for _ in'_'*n:
 a=input();s+=a;i=s
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
print(3**n+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%M

Solution (Python):
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=d[:]
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
print(z+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%M

Solution (Python):
from math import ceil


N = int(input())
A = [int(input()) for i in range(N)]

MOD = 998244353


S = sum(A)

dp = [0 for _ in range(S + 1)]
dp[0] = 1

dp2 = [0 for _ in range(S // 2 + 1)]
dp2[0] = 1


for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = (2 * dp[i] + dp[i - a]) % MOD
    for i in range(a - 1, -1, -1):
        dp[i] = (2 * dp[i]) % MOD
    for i in range(S // 2, a - 1, -1):
        dp2[i] = (dp2[i] + dp2[i - a]) % MOD


ans = (3**N - 3 * sum(dp[ceil(S / 2):]) + (
    3 * dp2[S // 2] if S % 2 == 0 else
    0
)) % MOD


print(ans)

Solution (Python):
M,z,s=998244353,1,0
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for a in A:
 a=int(a);s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
print((z+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%M)

Solution (Python):
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
print(z+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%M

Solution (Python):
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print(z+~s%2*e[i+1]*3)%M

Solution (Python):
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print(z+~s%2*e[s//2]*3)%M

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
S = sum(A)
MOD = 998244353

ans = pow(3,N,MOD)

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
dp2 = [[0]*(S+1) for i in range(N+1)]
dp2[0][0] = 1

suma = 0
for i,a in enumerate(A):
    for j in range(suma + 1):
        dp[i+1][j] += dp[i][j]*2
        dp[i+1][j] %= MOD
        dp[i+1][j+a] += dp[i][j]
        dp[i+1][j+a] %= MOD
        dp2[i+1][j] += dp2[i][j]
        dp2[i+1][j] %= MOD
        dp2[i+1][j+a] += dp2[i][j]
        dp2[i+1][j+a] %= MOD
    suma += a

ans -= sum(dp[-1][(S+1)//2:])*3
ans %= MOD

if S%2==0:
    tmp = dp2[-1][S//2]*3
    ans += tmp
    ans %= MOD

print(ans)

Solution (Python):
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print(z+~s%2*e[s//2]*3)%M

Solution (Python):
M=998244353
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print((z+~s%2*e[s//2]*3)%M)