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):
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)

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
z+=~s%2*e[s//2]*3
print(z%M)

Solution (Python):
M=998244353
d=[0]*90301
d[0]=1
e=[0]*90301
e[0]=1
z=1
s=0
for _ in range(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
z+=~s%2*e[s//2]*3
print z%M

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

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

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

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

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

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

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

M = 998244353

S = sum(A)
dp = [0 for _ in range(S + 1)]
dp[0] = 1
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = (2 * dp[i] + dp[i - a]) % M
    for i in range(a - 1, -1, -1):
        dp[i] = (2 * dp[i]) % M
dp2 = [0 for _ in range(S + 1)]
dp2[0] = 1
for a in A:
    for i in range(S, a - 1, -1):
        dp2[i] = (dp2[i] + dp2[i - a]) % M
s = 0
for i in range((S + 1) // 2, S + 1):
    s = (s + dp[i]) % M
ans = (3**N - 3 * s) % M
if S % 2 == 0:
    ans = (3**N - 3 * s + 3 * dp2[S // 2]) % M
print(ans)

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

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

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

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

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

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

Solution (Python):
import math
import numpy as np

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





dp0 = np.zeros((N + 1, S + 1), dtype=np.int64)






dp1 = np.zeros((N + 1, S // 2 + 1), dtype=np.int64)


dp0[0, 0] = 1
dp1[0, 0] = 1


for i, x in enumerate(A):

    
    
    dp0[i+1, :] += dp0[i, :] * 2 % MOD

    
    
    
    dp0[i+1, x:] += dp0[i, :-x]

    
    
    dp1[i+1, :] += dp1[i, :] % MOD

    
    dp1[i+1, x:] += dp1[i, :-x]



not_satisfy = np.sum(dp0[N][math.ceil(S/2):])


double_reduct = 0 if S % 2 == 1 else dp1[N][S/2]



ans = (3 ** N - 3 * not_satisfy + 3 * double_reduct) % MOD
print(ans)

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((N + 1, m1), dtype='int64')
    ab[0, m] = 1
    for i in range(N):
        c = a[i]
        ab[i + 1, :-c] = (2 * ab[i, :-c] + ab[i, c:]) % 998244353
        ab[i + 1, -c:] = (2 * ab[i, -c:] + ab[i, m]) % 998244353
    return ab[N, 0]


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


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

Solution (Python):
M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]
		d[i+a]%=M
		d[i]*=2
		d[i]%=M
		e[i+a]+=e[i]
		e[i+a]%=M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])

Solution (Python):
M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]%M
		d[i]*=2
		e[i+a]+=e[i]%M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])

Solution (Python):
N=int(input())
S=[int(input()) for i in range(N)]
mod=998244353
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

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

dp[0][0]=2
dp[0][S[0]]=1
dp2[0][0]=1
dp2[0][S[0]]=1
for i in range(1,N):
    for j in range(sum_S+1):
        dp[i][j]=mul(dp[i-1][j],2)
        if j-S[i]>=0 and dp[i-1][j-S[i]]!=0:
            dp[i][j]=add(dp[i][j],dp[i-1][j-S[i]])

        if j<=sum_S//2:
            dp2[i][j]=dp2[i-1][j]
            if j-S[i]>=0 and dp2[i-1][j-S[i]]!=0:
                dp2[i][j]=add(dp2[i][j],dp2[i-1][j-S[i]])

if sum_S%2==0:
    print((pow(3,N)-sum(dp[N-1][sum_S//2:])*3+dp2[N-1][-1]*3)%mod)
else:
    print((pow(3,N)-sum(dp[N-1][sum_S//2+1:])*3)%mod)

Solution (Python):
import numpy as np

mod = 998244353


def sum_mod(v):
    ans = 0
    for i in range(1, len(v)):
        ans = (ans + v[i]) % mod
    return ans


n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
A = sum(a)

dp = np.zeros((n + 1, A + 1), dtype=int)
dp2 = np.zeros((n + 1, A + 1), dtype=int)
dp[0][0] = 1
dp2[0][0] = 1
for t in range(1, n + 1):
    dp[t, :] = dp[t - 1, :] * 2 % mod
    dp2[t, :] = dp2[t - 1, :] % mod
    dp[t, a[t - 1]:] += dp[t - 1, :-a[t - 1]] % mod
    dp2[t, a[t - 1]:] += dp2[t - 1, :-a[t - 1]] % mod


ans = 3 ** n % mod
ans -= np.sum(dp[n][(A + 1) // 2:]) * 3 % mod
if A % 2 == 0:
    ans += dp2[n][A // 2] * 3 % mod
print(ans % mod)

Solution (Python):
import sys
from itertools import accumulate


MOD = 998244353
fin = sys.stdin.readline
N = int(fin())
a_list = [int(fin()) for _ in range(N)]
max_a = max(a_list)
sum_a = sum(a_list)

dp = [[0] * (sum_a + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i, a in enumerate(a_list, start=1):
    for m in range(len(dp[i])):
        dp[i][m] = 2 * dp[i - 1][m] + (dp[i - 1][m - a] if m - a >= 0 else 0)
        dp[i][m] %= MOD


if sum_a % 2 == 0:
    bound_dp = [[0] * (sum_a // 2 + 1) for _ in range(N + 1)]
    bound_dp[0][0] = 1
    for i, a in enumerate(a_list, start=1):
        for m in range(len(bound_dp[i])):
            bound_dp[i][m] = bound_dp[i - 1][m] + (bound_dp[i - 1][m - a] if m - a >= 0 else 0)
            bound_dp[i][m] %= MOD
    
    print((3 ** N - 3 * sum(dp[N][sum_a // 2:]) + 3 * bound_dp[N][sum_a // 2]) % MOD)
else:
    print((3 ** N - 3 * sum(dp[N][sum_a // 2 + 1:])) % MOD)

Solution (Python):
MOD = 998244353

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

dp = [ [0] * (SUM + 1) for _ in range(N+1) ]
dp2 = [ [0] * (SUM + 1) for _ in range(N+1) ]

dp[0][0] = 1
dp2[0][0] = 1
for i in range(N):
    a = A[i]
    for r in range(0, SUM-a +1):
        
        dp[i+1][r+a] = ( dp[i+1][r+a] + dp[i][r] ) % MOD
        dp2[i+1][r+a] = ( dp2[i+1][r+a] + dp2[i][r] ) % MOD


    for r in range(0, SUM + 1):
        
        
        dp[i+1][r] = (dp[i+1][r] +  dp[i][r] * 2 ) % MOD
        dp2[i+1][r] = (dp2[i+1][r] +  dp2[i][r]  ) % MOD

if SUM % 2 ==0:
    notans = sum(dp[N][ SUM//2 : ]) * 3 % MOD

    notans = ( notans - 3 * dp2[N][SUM//2] ) %MOD
    cand = pow(3, N, MOD)

    print(  (cand - notans + MOD) % MOD  )
else:
    notans = sum(dp[N][ SUM//2 + 1: ]) * 3 % MOD
    cand = pow(3, N, MOD)
    print(  (cand - notans + MOD) % MOD  )

Solution (Python):

import numpy as np
N = int(input())
a = np.array([int(input()) for i in range(N)])
mod =998244353
sum_a = np.sum(a)
dp =  np.zeros((N+1,sum_a+1))
half_dp = np.zeros((N+1,sum_a//2+1))
dp[0][0], half_dp[0][0] = 1, 1

for i in range(1,N+1):
    dp[i,:] += dp[i-1,:]*2 % mod
    dp[i,a[i-1]:] +=  dp[i-1, :-a[i-1]] % mod
    half_dp[i,:] +=  half_dp[i-1,:] % mod
    half_dp[i,a[i-1]:] += half_dp[i-1,:-a[i-1]] % mod

all_combination = 3**N % mod
half_sum_a = (sum_a //2) if sum_a % 2 == 0 else (sum_a//2)+1 
p = np.sum(dp[N][half_sum_a:])
c = half_dp[N][half_sum_a] if sum_a % 2==0 else 0
print(int(all_combination - 3 * p + 3 * c) % mod)

Solution (Python):
import numpy as np

mod = 998244353
N = int(input())
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

exc = np.sum(dp[N, (sum_a+1)//2:]) % mod
res = 3**N % mod - exc * 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

mod = 998244353
N = int(input())
a = np.array([int(input()) for i in range(N)])
sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
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

exc = np.sum(dp[N, (sum_a+1)//2:]) % mod
res = 3**N % mod - exc * 3

if sum_a % 2 == 0:
    dp = np.zeros((N+1, sum_a+1))
    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(int(res % mod))

Solution (Python):

from sys import stdin
import numpy as np



s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


MOD = 998244353

N = d_in()
total = 3 ** N - (2**N - 2) * 3 - 3

a_list = []
for _ in range(N):
    a_list.append(d_in())
sum_a = sum(a_list)




dp = np.zeros((N+1, 3, 1 + (sum_a+1)//2), dtype=int)
dp[0, 2, 0] = 1

for i in range(1, N+1):
    a = a_list[i-1]

    
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    
    dp[i, 0, :] += (dp[i-1, 0, :] + dp[i-1, 1, :]) * 2
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 2, :]

    dp[i, :, :] %= MOD

print((total - dp[-1, 0, -1] * 3) % MOD)

Solution (Python):
N, *A = map(int, open(0).read().split())
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S//2+1):
    ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)

Solution (Python):

from sys import stdin
import numpy as np




s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


MOD = 998244353

N = d_in()
total = 3 ** N - (2**N - 2) * 3 - 3

a_list = []
for _ in range(N):
    a_list.append(d_in())
sum_a = sum(a_list)




dp = np.zeros((N+1, 3, 1 + (sum_a+1)//2), dtype=int)
dp[0, 2, 0] = 1

for i in range(1, N+1):
    
    a = a_list[i-1]
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    
    dp[i, 0, :] += (dp[i-1, 0, :] + dp[i-1, 1, :]) * 2
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 2, :]

    if i % 10 == 0:
        dp[i, :, :] %= MOD

print((total - dp[-1, 0, -1] * 3) % MOD)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
sum_len = sum(a)
max_len = -((-sum_len)//2)
MOD = 998244353


dp = [[0]*(sum_len+1) for i in range(n+1)]
dp[0][0]= 1
for i in range(n):
    for len in range(sum_len+1):
        
        dp[i+1][len] = dp[i][len]*2
        
        if 0 <= len-a[i]:
            dp[i+1][len] += dp[i][len-a[i]]
        dp[i+1][len] %= MOD

            

dp2 = [[0]*(sum_len+1) for i in range(n+1)]
dp2[0][0]= 1
for i in range(n):
    for len in range(sum_len+1):
        
        dp2[i+1][len] = dp2[i][len]
        
        if 0 <= len-a[i]:
            dp2[i+1][len] += dp2[i][len-a[i]]
        dp2[i+1][len] %= MOD

if sum_len % 2 == 0:
    ans = pow(3,n,MOD) - 3*sum(dp[n][max_len:]) + 3*dp2[n][max_len]
else:
    ans = pow(3,n,MOD) - 3*sum(dp[n][max_len:])
ans %= MOD
print(ans)

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

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1
tmp_sum = 0

for a in A:
    for i in reversed(range(tmp_sum + 1)):
        dp1[i] %= MOD
        dp2[i] %= MOD
        dp1[i + a] += dp1[i]
        dp1[i] <<= 1
        dp2[i + a] += dp2[i]
    tmp_sum += a


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
mod = 998244353
n = int(input())
a = [int(input()) for i in range(n)]
d = max(a)
go = sum(a)
dp = [[0]*(go+d+1) for j in range(n+1)]
dp[0][0] = 1
dp2 = [[0]*(go+d+1) for j in range(n+1)]
dp2[0][0] = 1
for i in range(n):
    for j in range(go):
            dp[i+1][j+a[i]] += dp[i][j]
            dp[i+1][j] += dp[i][j]*2
            dp[i+1][j+a[i]] %= mod
            dp[i+1][j] %= mod

            dp2[i+1][j+a[i]] += dp2[i][j]
            dp2[i+1][j] += dp2[i][j]
            dp2[i+1][j+a[i]] %= mod
            dp2[i+1][j] %= mod

zen = 3**n
zen %= mod
if go %2 == 1:
    print((zen - sum(dp[n][go//2+1:])*3)%mod)
else:
    print((zen - sum(dp[n][go//2:])*3 + dp2[n][go//2]*3)%mod)

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

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1
tmp_sum = 0

for a in A:
    tmp_sum += a
    for i in reversed(range(tmp_sum + 1)):
        if i - a >= 0:
            
            dp1[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1[i] = (dp1[i] * 2) % MOD
            dp2[i] = dp2[i]


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)

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

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1


for a in A:
    for i in reversed(range(sum_A + 1)):
        if i - a >= 0:
            
            dp1[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1[i] = (dp1[i] * 2) % MOD
            dp2[i] = dp2[i]


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)

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

S = sum(A)

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

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

for i in range(N):
    a = A[i]
    x = 0
    while x <= S:
        if x + a <= S:
            dp[i+1][x+a] += dp[i][x] % MOD
            dp2[i+1][x+a] += dp2[i][x] % MOD
        dp[i+1][x] += dp[i][x] * 2 % MOD
        dp2[i+1][x] += dp2[i][x] % MOD
        x += 1


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

print(ans % MOD)

Solution (Python):
N, *A = map(int, open(0).read().split())
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S+1):
    if L <= S-L:
        ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)

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

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1


for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        if i - a >= 0:
            
            dp1_[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2_[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1_[i] = (dp1[i] * 2) % MOD
            dp2_[i] = dp2[i]
    dp1, dp2 = dp1_, dp2_


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)

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

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        
        if i + a <= sum_A:
            dp1_[i + a] = (dp1_[i + a] + dp1[i]) % MOD
            dp2_[i + a] = (dp2_[i + a] + dp2[i]) % MOD
        
        dp1_[i] = (dp1_[i] + dp1[i] * 2) % MOD
        dp2_[i] = (dp2_[i] + dp2[i]) % MOD
    dp1 = dp1_
    dp2 = dp2_

ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)

Solution (Python):
import sys

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

s = sum(aaa)
dp1 = [0] * (s + 1)
dp2 = [0] * (s + 1)
dp1[0] = 1
dp2[0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        dp1[i + a] += dp1[i]
        dp1[i] *= 2
        dp2[i + a] += dp2[i]
    for i in range(tmp_sum, -1, -1):
        dp1[i] %= MOD
        dp2[i] %= MOD
    tmp_sum += a

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

Solution (Python):
N = int(input())
mod = 998244353





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

sum_now = 0
DP = [[0] * (sum(aaa)+1) for i in range(N)]
DP2 = [[0] * (sum(aaa)+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	for j in range(sum_now + 1):
		DP[i][j] += DP[i-1][j] * 2
		DP[i][j] %= mod
		DP[i][j + a] += DP[i-1][j]

		DP2[i][j] += DP2[i-1][j]
		DP2[i][j] %= mod
		DP2[i][j + a] += DP2[i-1][j]

	sum_now += a


minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum(aaa) %2 == 0):
	num_too_long -= DP2[N-1][int(sum(aaa) /2)]


print((3** N - num_too_long * 3) % mod )

Solution (Python):
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]


D = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D[0][0] = 1

D2 = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(PS[i]+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] = (D[i+1][j] + D[i][j] * 2) % mod
        D[i+1][j+A[i]] = (D[i+1][j+A[i]] + D[i][j]) % mod

for i in range(N):
    for j in range(PS[i]+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] = (D2[i+1][j] + D2[i][j]) % mod
        D2[i+1][j+A[i]] = (D2[i+1][j+A[i]] + D2[i][j]) % mod

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[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)]
w = sum(a)
mod =998244353

dp = [[0]*(w+1) for i in range(n)]

cnt = a[0]
dp[0][a[0]] = 1
dp[0][0] = 2
for i in range(1,n):
    cnt += a[i]
    for j in range(cnt+1):
        dp[i][j] = dp[i-1][j]*2
        if j >= a[i]:
            dp[i][j] += dp[i-1][j-a[i]]
        
        dp[i][j] = dp[i][j]%mod


s = w//2+1
if w %2 == 0:
    d = [[0]*(s+1) for i in range(n)]
    d[0][0] = 1
    d[0][a[0]] = 1
    cnt = a[0]

    for i in range(1,n):
        cnt += a[i]
        for j in range(min(cnt+1,s+1)):
            d[i][j] = d[i-1][j]
            if j >= a[i]:
                d[i][j] += d[i-1][j-a[i]]
            d[i][j] = d[i][j]%mod
    mns = d[-1][w//2]
if w%2 == 0:
    s -= 1
cnt = 0
for i in range(s,w+1):
    cnt += dp[-1][i]
    cnt = cnt%mod

res = (pow(3,n,mod)-cnt*3)%mod

if w % 2 == 0:
    res = (res+mns*3)%mod
print(res)

Solution (Python):

N = int(input())
a_list = [0]*N
for i in range(N):
    a_list[i] = int(input())

L = 90001
LARGE = 998244353

DP = [0]*L
DP[0] = 1
for i in range(N):
    for j in range(L-1, a_list[i]-1, -1):
        DP[j] = (2*DP[j] + DP[j - a_list[i]]) % LARGE
    for j in range(a_list[i]-1, -1, -1):
        DP[j] = (2*DP[j]) % LARGE

DP2 = [0]*L
DP2[0] = 1
for i in range(N):
    for j in range(L-1, a_list[i]-1, -1):
        DP2[j] = (DP2[j] + DP2[j - a_list[i]]) % LARGE
    for j in range(a_list[i]-1, -1, -1):
        DP2[j] = (DP2[j]) % LARGE
S = sum(a_list)
if S % 2 == 0:
    h = S // 2
    res = ((3**N % LARGE) - (3*sum(DP[(h):]) % LARGE) + 3*DP2[h]) % LARGE
else:
    h = S // 2 + 1
    res = ((3**N % LARGE) - (3*sum(DP[(h):]) % LARGE)) % LARGE
print(res)

Solution (Python):
N = int(input())
mod = 998244353




 
aaa = [int(input()) for _ in range(N)]
 
sum_now = 0
DP = [[0] * (sum(aaa)+1) for i in range(N)]
DP2 = [[0] * (sum(aaa)+1) for i in range(N)]
 
a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1
 
DP2[0][0] = 1
DP2[0][a] = 1
 
sum_now += a
 
for i in range(1, N):
	a = aaa[i]
	for j in range(sum_now + 1):
		DP[i][j] += DP[i-1][j] * 2
		DP[i][j] %= mod
		DP[i][j + a] += DP[i-1][j]
 
		DP2[i][j] += DP2[i-1][j]
		DP2[i][j] %= mod
		DP2[i][j + a] += DP2[i-1][j]
 
	sum_now += a
 

minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum(aaa) %2 == 0):
	num_too_long -= DP2[N-1][int(sum(aaa) /2)]


print((3** N - num_too_long * 3) % mod )

Solution (Python):
N = int(input())
A = [abs(int(input())) for _ in range(N)]

s = sum(A)

def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  
  return mulmod(p, powermod(q,mod-2,mod), mod)

mod = 998244353

dp = [[0]*(s+1) for _ in range(N)]

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

for i in range(1,N):
  for j in range(A[i]):
    dp[i][j] = (dp[i-1][j]*2) %mod
  for j in range(A[i], temp_sum+1):
    dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-A[i]]) %mod
  for j in range(temp_sum+1, temp_sum+1 + A[i]):
    dp[i][j] = (dp[i-1][j-A[i]]) %mod
  temp_sum += A[i]


def part_sum(a,A):
  p=mod
  
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: 
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: 
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

if s%2 != 0:
    answer = (powermod(3, N, mod) - 3*sum(dp[N-1][(s+1)//2:]))%mod
else:
    answer = (powermod(3, N, mod) - 3*(sum(dp[N-1][(s+1)//2:]) - ps))%mod



print(answer)

Solution (Python):
N = int(input())
mod = 998244353





aaa = [int(input()) for _ in range(N)]
sum_aaa = sum(aaa)

sum_now = 0
DP = [[0] * (sum_aaa+1) for i in range(N)]
DP2 = [[0] * (sum_aaa+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	sum_now += a
	for j in range(sum_now + 1):

		if (j >= a):
			DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-a]
		else:
			DP[i][j] = DP[i-1][j]*2

		while (DP[i][j] > mod):
			DP[i][j] -= mod

	for j in range(min(sum_now + 1, int(sum_aaa /2)+1)):
		if (j >= a):
			DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-a]
		else:
			DP2[i][j] = DP2[i-1][j]

		while (DP2[i][j] > mod):
			DP2[i][j] -= mod


minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum_aaa %2 == 0):
	num_too_long -= DP2[N-1][int(sum_aaa /2)]


print((3** N - num_too_long * 3) % mod )