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):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
MOD = 998244353
N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2
    dp[a:] += prev[:-a]
    dp %= MOD
ans = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    ans += dp[S//2] * 3
ans %= MOD
print(ans)

Solution (Python):
from numpy import zeros, roll

mod = 998244353

N, *A = map(int, open(0))

S = sum(A)

dp1 = zeros(S + 1, dtype=int)
dp1[0] = 1

dp2 = zeros(S + 1, dtype=int)
dp2[0] = 1

for a in A:
    dp1 = (2 * dp1 + roll(dp1, a)) % mod
    dp2 = (dp2 + roll(dp2, a)) % mod

M = (S + 1) // 2

res = 3 * dp1[M:].sum()
if S % 2 == 0:
    res -= 3 * dp2[M]

print((pow(3, N, mod) - res) % mod)

Solution (Python):
n = int(input())
A = tuple(int(input()) for _ in range(n))
S = sum(A)
mod = 998244353
ans = pow(3, n, mod)
cnt = 0
dp = [[0]*(S+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
  for k in range(S+1):
    if k >= a:
      dp[i+1][k] = dp[i][k]*2 + dp[i][k-a]
    else:
      dp[i+1][k] = dp[i][k]*2
    dp[i+1][k] %= mod
for k in range((S+1)//2, S+1):
  ans -= dp[n][k]*3
  ans %= mod
if S%2 == 0:
  dp = [0]*(S//2+1)
  dp[0] = 1
  for i, a in enumerate(A):
    for k in range(S//2, -1, -1):
      if k >= a:
        dp[k] += dp[k-a]
  ans += dp[S//2]*3
  ans %= mod
print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())


N = I()
A = [0] + [I() for _ in range(N)]
s = sum(A)
mod = 998244353

dp1 = [[0]*(s+1) for _ in range(N+1)]  
dp1[0][0] = 1
for i in range(1,N+1):
    a = A[i]
    for j in range(s+1):
        if j >= a:
            dp1[i][j] = dp1[i-1][j]*2 + dp1[i-1][j-a]
        else:
            dp1[i][j] = dp1[i-1][j]*2
        dp1[i][j] %= mod

dp2 = [[0]*(s//2+1) for _ in range(N+1)]  
dp2[0][0] = 1
for i in range(1,N+1):
    a = A[i]
    for j in range(s//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]
        dp2[i][j] %= mod

a = sum(dp1[N][i] for i in range((s+1)//2,s+1))
a %= mod
if s % 2 == 0:
    a -= dp2[N][s//2]

ans = pow(3,N,mod)-a*3
ans %= mod
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [int(input()) for _ in range(n)]
M = 998244353
s = sum(a)
l = s//2 + int(s%2==1)

dp = [0]*(s+1)
dp2 = [0]*(s+1)
dp[0] = pow(2, n, M)
dp2[0] = 1
inv2 = pow(2, M-2, M)
for i in range(1,n+1):
    num = a[i-1]
    for j in range(s, -1, -1):
        if j>=num:
            dp[j] += dp[j-num]*inv2
            dp[j] %= M
            dp2[j] += dp2[j-num]
            dp2[j] %= M
val = sum(dp[i] for i in range(l, s+1)) * 3
if s%2==0:
    val -= dp2[s//2]*3
ans = (pow(3,n,M) - val)%M
print(ans%M)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353

    """
    aiが300以下なのが嬉しい，総和でなんかできる．
    dp[i][j]でi番目まで見て合計がj，j<=N*max(a)なので合計O(N^2 max(a))，これでRの通り数が求まるがGB用に何が残っているのかわからん-
    余事象，R>=sum(a)/2 ならダメなわけで
    
    """
    N=I()
    A=[0]*N
    for i in range(N):
        A[i]=I()
    
    S=sum(A)
    
    dp=[[0]*(S+1) for _ in range(N+1)]
    
    dp[0][0]=1
    
    for i in range(N):
        a=A[i]
        for j in range(S+1):
            dp[i+1][j]=(dp[i+1][j] + dp[i][j]*2)%mod
            if j+a<=S:
                dp[i+1][j+a]=(dp[i+1][j+a] + dp[i][j])%mod
    
    rem=0
    for j in range((S+1)//2,S+1):
        rem=(rem+dp[-1][j])%mod
    ans=pow(3,N,mod)-rem*3
    ans%=mod
        
    if S%2==0:
        
        dp2=[[0]*(S+1) for _ in range(N+1)]
        
        dp2[0][0]=1
        
        for i in range(N):
            a=A[i]
            for j in range(S+1):
                dp2[i+1][j]=(dp2[i+1][j] + dp2[i][j])%mod
                if j+a<=S:
                    dp2[i+1][j+a]=(dp2[i+1][j+a] + dp2[i][j])%mod
                    
        temp=dp2[-1][S//2]
        ans+=temp*3
        
    
    print(ans%mod)
    
    
    
            

main()

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

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

ans = pow(3, N, mod)
S = sum(a)
M = 300 * N

dp1 = [0] * (M + 1)
dp1[0] = 1
for i in a:
    ndp1 = [0] * (M + 1)
    for j in range(i, M + 1)[::-1]:
        ndp1[j] = (ndp1[j] + dp1[j - i]) % mod
    for j in range(M + 1):
        ndp1[j] = (ndp1[j] + dp1[j] * 2) % mod
    dp1 = ndp1
tmp = 0
for j in range((S + 1) // 2, M + 1):
    tmp = (tmp + dp1[j]) % mod
ans = (ans - 3 * tmp) % mod

dp2 = [0] * (2 * M + 1)
dp2[0] = 1
for i in a:
    ndp2 = [0] * (2 * M + 1)
    for j in range(i - M, M - i + 1):
        ndp2[j - i] = (ndp2[j - i] + dp2[j]) % mod
        ndp2[j + i] = (ndp2[j + i] + dp2[j]) % mod
    dp2 = ndp2
ans = (ans + 3 * dp2[0]) % mod

print(ans)

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
mod=998244353
DP=[[0]*90001 for i in range(N+1)]
DP[0][0]=pow(2,N,mod)
inv2=((mod+1)>>1)
for i in range(N):
  for j in range(300*i+1):
    DP[i+1][j]=(DP[i][j]+DP[i+1][j])%mod
    DP[i+1][j+A[i]]=DP[i][j]*inv2%mod
P=(pow(3,N,mod)-sum(DP[N][((sum(A)+1)>>1):])*3)%mod
DP=[[0]*90001 for i in range(N+1)]
DP[0][0]=1
for i in range(N):
  for j in range(300*i+1):
    DP[i+1][j]=(DP[i][j]+DP[i+1][j])%mod
    DP[i+1][j+A[i]]=DP[i][j]%mod
if sum(A)&1==0:
  P+=DP[N][sum(A)>>1]*3
print(P%mod)

Solution (Python):
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [0] * (s * 2 + 1)

dp[s] = 1
for ai in a:
    ndp = [0] * (s * 2 + 1)
    for j in range(s * 2 + 1):
        if dp[j] != 0:
            ndp[j+ai] += dp[j]
            ndp[j+ai] %= MOD
            ndp[j-ai] += dp[j] * 2
            ndp[j-ai] %= MOD
    dp = ndp




dp2 = [0] * (s * 2 + 1)
dp2[s] = 1
for ai in a:
    ndp2 = [0] * (s * 2 + 1)
    for j in range(s * 2 + 1):
        if dp2[j] != 0:
            ndp2[j+ai] += dp2[j]
            ndp2[j+ai] %= MOD
            ndp2[j-ai] += dp2[j]
            ndp2[j-ai] %= MOD
    dp2 = ndp2

ans = (pow(3, n, MOD) - ((sum(dp[s:]) - dp2[s] * 2) * 3 + dp2[s] * 3)) % MOD
print(ans)

Solution (Python):

mod =998244353

def main():
    
    
    N=int(input())
    A=[int(input()) for i in range(N)]
    M=(sum(A)-1)//2
    S=sum(A)
    
    
    Alls = pow(3,N,mod) 
    
    case2=0
    
    dp=[[0 for i in range(90001)] for j in range(N+1)]
    dp[0][0]=1
    for i in range(1,N+1):
        v=A[i-1]
        for j in range(90001):
            if j>=v:
                dp[i][j]= dp[i-1][j-v]+ 2*dp[i-1][j]
            else:
                dp[i][j]=2*dp[i-1][j]
            dp[i][j]%=mod   

    if S%2!=0:
        
        for i in range(M+1,90001):
            case2+=3*dp[N][i]
            case2%=mod
    if S%2==0:
        
        for i in range(M+1,90001):
            case2+=3*dp[N][i]
            case2%=mod
        
        
        sub_dp=[[0 for i in range(90001)] for j in range(N+1)]
        sub_dp[0][0]=1
        for i in range(1,N+1):
            v=A[i-1]
            for j in range(90001):
                if j>=v:
                    sub_dp[i][j]= sub_dp[i-1][j]+sub_dp[i-1][j-v]
                else:
                    sub_dp[i][j]=sub_dp[i-1][j]
                sub_dp[i][j]%=mod
        case2-=3*sub_dp[N][S//2]
        case2%=mod
    ans=Alls-case2
    print(ans%mod)
    return
        


if __name__ =="__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
mod = 998244353
dp = [0] * 900001
dp2 = [0] * 900001
dp[0] = 1
dp2[0] = 1
sm = 0
for _ in range(N):
  x = int(input())
  for y in range(900000, -1, -1):
    if dp[y]:
      dp[x + y] += dp[y]
      dp[x + y] %= mod
      dp2[x + y] += dp2[y]
      dp2[x + y] %= mod
      dp[y] *= 2
      dp[y] %= mod
  sm += x
res = 0
for x in range(sm + 1):
  if x > sm - x:
    res += max(0, dp[x])
    res %= mod
  elif x == sm - x:
    res += dp[x] - dp2[x]
    res %= mod

print((pow(3, N, mod) - res * 3) % mod)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,read().split()))
mod = 998244353

sum_a = sum(a)
dp = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_rg = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_rb = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_r = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_r[0][0] = 1
tot = 0

for i in range(1,n+1):
    ai = a[i-1]
    tot += ai
    for j in range(tot+1):
        dp_rg[i][j] += dp_rg[i-1][j] + dp_r[i-1][j]
        dp_rb[i][j] += dp_rb[i-1][j] + dp_r[i-1][j]
        dp[i][j] += dp[i-1][j] * 2 + dp_rb[i-1][j] + dp_rg[i-1][j]

        if(j >= ai):
            dp_r[i][j] += dp_r[i-1][j-ai]
            dp_rg[i][j] += dp_rg[i-1][j-ai]
            dp_rb[i][j] += dp_rb[i-1][j-ai]
            dp[i][j] += dp[i-1][j-ai]
        dp_rg[i][j] %= mod
        dp_rb[i][j] %= mod
        dp[i][j] %= mod

r_over = sum(dp[-1][(1+sum_a)//2:]) % mod
ans = (pow(3,n,mod) - 3*pow(2,n,mod) + 3 - 3*r_over)%mod
print(ans)

Solution (Python):
def main():
    import numpy as np
    n = int(input())
    a = sorted([int(input()) for _ in [0]*n])
    dp = np.array([1], dtype=np.int64)
    DP = np.array([1], dtype=np.int64)
    s = 1
    mod = 998244353
    for i in a:
        dp2 = np.concatenate([dp, np.zeros(i, dtype=np.int64)])
        DP2 = np.concatenate([DP, np.zeros(i, dtype=np.int64)])
        dp2[i:] = (dp2[i:]+2*dp) % mod
        DP2[i:] = (DP2[i:]+DP) % mod
        dp = dp2
        DP = DP2
        s += i
    ALL = sum(dp)
    A = sum(dp[(s-1)//2+1:])
    if s % 2 == 1:
        B = DP[s//2]
    else:
        B = 0
    print((3*A-2*ALL+3*B) % mod)


main()

Solution (Python):
def main():
    n = int(input())
    a = sorted([int(input()) for _ in [0]*n])
    dp = [1]
    DP = [1]
    s = 1
    mod = 998244353
    for i in a:
        dp2 = dp+([0]*i)
        DP2 = DP+([0]*i)
        for j in range(s):
            dp2[i+j] = (dp2[i+j]+2*dp[j]) % mod
            DP2[i+j] = (DP2[i+j]+DP[j]) % mod
        dp = dp2
        DP = DP2
        s += i
    ALL = sum(dp)
    A = sum(dp[(s-1)//2+1:])
    if s % 2 == 1:
        B = DP[s//2]
    else:
        B = 0
    print((3*A-2*ALL+3*B) % mod)


main()

Solution (Python):
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
inv=pow(2,mod-2,mod)
S=sum(A)

dp=[0 for j in range(S+1)]
sub=[0 for j in range(S+1)]
dp[0]=pow(2,N,mod)
dp[A[0]]=pow(2,N-1,mod)
sub[0]=1
sub[A[0]]=1

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

if S%2==1:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[i]
        ans%=mod
    print(ans)
else:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[i]
        ans%=mod
    ans+=3*sub[S//2]
    ans%=mod
    print(ans)

Solution (Python):
n=int(input())
a=[int(input()) for _ in range(n)]
mod=998244353
s=sum(a)

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

dp2=[[0]*(s+1) for _ in range(n)]
dp2[0][0]=1;dp2[0][a[0]]=1
for i in range(n-1):
    for j in range(s+1):
        dp2[i+1][j]=(dp2[i+1][j]+dp2[i][j])%mod
        if j+a[i+1]<=s: dp2[i+1][j+a[i+1]]=(dp2[i+1][j+a[i+1]]+dp2[i][j])%mod

if s%2==0:
    inable=( sum(dp[n-1][s//2:]) - dp2[n-1][s//2] )*3%mod
else:
    inable=( sum(dp[n-1][s//2+1:]) )*3 %mod

ans=1
for _ in range(n):
    ans=ans*3%mod
ans=(ans-inable)%mod
print(ans)

Solution (Python):
"""
Writer:SPD_9X2
https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_d

愚直全探索は 0(3**N)
O(N**3)位までは計算量を落とさないといけない

ありうる辺の長さ全列挙→むりぽ
短い2辺の和 < 長い辺の和　なら構成不可能
構成不可能分配の方を数える？

少なくとも各辺に1本分配する場合、
構成不可能な場合の最長辺の長さは必ず総延長の半分以上となる
総延長の半分以上となる取り方の数を数えて引けばよい？

長さとしてありうるのは 300**2 までしかありえないので、
dp推移をO(1)でやれば解けそう

具体的なdp推移を考えてみる
最長辺を赤と決めてあげてよい？

全部赤に割り振って減らしていく
→Nこの中からいくつか取って、半分以上の長さにする方法を網羅できる

調整
→最長3色分をやると、2色に半分ずつ行った時をダブルカウントしてるので処理する

解けた！！ O(sum(a)*N)

→解けてねぇ！！！！！！！
1本の辺の作り方を数えても結局残りの辺の数によって分配が依存してしまう…

N本からA本選んで長さの半分を超える方法がいくつあるか数えればよい
そうすれば残りの分配をO(1)でできる

=======答えを見た========

最初の方針で行けるやん…？
DP[r] = 赤の数がrであるような「塗り分けの個数」

"""

import math
mod = 998244353
N = int(input())

a = []

for i in range(N):

    A = int(input())
    a.append(A)

asum = sum(a)
lis = [0] * ( asum + 1)
lis[0] = 1

for i in range(N):

    nlis = [0] * (asum+1)
    for j in range(asum+1):

        nlis[j] += lis[j] * 2
        nlis[j] %= mod
        if j+a[i] <= asum:
            nlis[j+a[i]] += lis[j]
            nlis[j+a[i]] %= mod

    lis = nlis


ans = pow(3,N,mod)


if asum % 2 == 1:
    for i in range( asum//2+1 , asum+1):
        ans -= lis[i] * 3
        ans %= mod

    print (ans)

else:
    for i in range( asum//2 , asum+1):
        ans -= lis[i] * 3
        ans %= mod

    
    

    lis2 = [0] * (asum+1)
    lis2[0] = 1

    for i in range(N):
        for j in range(asum-a[i],-1,-1):
            lis2[j+a[i]] += lis2[j]
            lis2[j+a[i]] %= mod

    ans += lis2[asum//2] * 3
    print (ans % mod)
        


"""
import math
mod = 998244353
N = int(input())

a = []

for i in range(N):

    A = int(input())
    a.append(A)

asum = sum(a)
lis = [0] * ( asum + 1)
lis[-1] = 1

for i in range(N):

    for j in range(len(lis)):

        if j - a[i] >= 0:
            lis[j-a[i]] += lis[j]
            lis[j-a[i]] %= mod

print (lis)
ans = pow(3,N,mod)
print (ans)

if asum % 2 == 1:
    for i in range( asum//2 , asum+1):
        ans -= lis[i] * 6
        ans %= mod

    print (ans)

"""

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

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

mod=998244353

ans=pow(3,N,mod)
S=sum(A)
dp=[0]*(S+1)
dp[0]=1
for u in A:
    h=[0]*(S+1)
    for i in range(u):
        h[i]=2*dp[i]%mod
    for i in range(u,S+1):
        h[i]=(dp[i-u]+2*dp[i])%mod
    dp=h

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

if S%2==0:
    dp=[0]*(S//2+1)
    dp[0]=1
    for u in A:
        h=[0]*(S//2+1)
        for i in range(u):
            h[i]=dp[i]
        for i in range(u,S//2+1):
            h[i]=(dp[i]+dp[i-u])%mod
        dp=h
    ans=(ans+dp[S//2]*3)%mod
    
print(ans)

Solution (Python):
import sys
from collections import Counter
readline = sys.stdin.readline

MOD = 998244353
N = int(readline())
A = [int(readline()) for _ in range(N)]
S = sum(A)
C = Counter()
C[0] = 1
for a in A:
    for k, v in C.copy().items():
        C[k] = (C[k] + v)%MOD
        C[k+a] = (C[k+a] + v)%MOD
cnt = 0
for k, v in C.items():
    if 2*k >= S:
        cnt = (cnt + v)%MOD

cnt2 = 0
if S%2 == 0:
    D = Counter()
    D[0] = 1
    for a in A:
        for k, v in D.copy().items():
            D[k+a] = (D[k+a] + v)%MOD
    cnt2 = D[S//2]
ans = pow(3, N, MOD) - 3*cnt + 3*cnt2
print(ans%MOD)

Solution (Python):
import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 998244353
    n = int(input())
    mx = 90005
    dp = np.zeros(mx, dtype="i8")
    dp2 = np.zeros(mx, dtype="i8")
    dp[0] = 1
    dp2[0] = 1
    sum_a = 0
    for _ in range(n):
        a = int(input())
        sum_a += a
        dp[mx - 1:a - 1:-1] = dp[mx - 1:a - 1:-1] * 2 + dp[mx - a - 1::-1]
        dp[:a] *= 2
        dp %= md
        dp2[mx - 1:a - 1:-1] += dp2[mx - a - 1::-1]
        dp2 %= md
    ng = np.sum(dp[(sum_a + 1) // 2:]) - np.sum(dp2[(sum_a + 1) // 2:]) * 2 + 1
    ng %= md
    total = (pow(3, n, md) - 3 * pow(2, n, md) + 3) % md
    print((total - ng * 3) % md)
    
    
    
    
    
    

main()

Solution (Python):

import sys
import numpy as np

MOD = 998244353

def main():
    n, *A = map(int, sys.stdin.read().split())
    S = sum(A)

    dp = np.zeros(S//2+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] = (dp[a:] + dp.copy()[:-a] * 2) % MOD
    
    ans = (pow(3, n, MOD) - dp.sum() * 3 % MOD) % MOD

    if S % 2 == 0:
        dp = np.zeros(S//2+1, dtype=np.int64)
        dp[0] = 1
        for a in A:
            dp[a:] = (dp[a:] + dp.copy()[:-a]) % MOD
        ans = (ans + dp[S//2] * 3) % MOD

    print(ans)


if __name__ == '__main__':
    main()

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):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n = I()
A = IR(n)



a_sum = sum(A)
dp1 = [0] * (a_sum + 1)
dp1[0] = 1
dp2 = [0] * (a_sum + 1)
dp2[0] = 1
for i in range(n):
    for j in range(a_sum, -1, -1):
        if j < A[i]:
            dp2[j] = dp2[j] * 2 % mod
        else:
            dp1[j] = (dp1[j] + dp1[j - A[i]]) % mod
            dp2[j] = (dp2[j] * 2 + dp2[j - A[i]]) % mod


ans = pow(3, n, mod)
for k in range((a_sum + 1) // 2, a_sum + 1):
    ans = (ans - dp2[k] * 3) % mod


if a_sum % 2 == 0:
    ans = (ans + dp1[a_sum // 2] * 3) % mod


print(ans)

Solution (Python):
mod = 998244353

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

S = sum(A)

dp1 = [[0] * (S+1) for _ in range(N+1)]
dp1[0][0] = 1
for i in range(N):
    for r in range(S+1):
        if r + A[i] < S+1:
            dp1[i+1][r+A[i]] += dp1[i][r]
            dp1[i+1][r+A[i]] %= mod
        dp1[i+1][r] += 2 * dp1[i][r]
        dp1[i+1][r] %= mod

dp2 = [[0] * (S+1) for _ in range(N+1)]
dp2[0][0] = 1
for i in range(N):
    for r in range(S+1):
        if r + A[i] < S+1:
            dp2[i+1][r+A[i]] += dp2[i][r]
            dp2[i+1][r+A[i]] %= mod
        dp2[i+1][r] += dp2[i][r]
        dp2[i+1][r] %= mod

res1 = sum(dp1[N][r] for r in range(-(-S//2), S+1))
res2 = dp2[N][S//2] if S % 2 == 0 else 0

ans = pow(3, N, mod) - (3*res1 - 3*res2)
ans %= mod
print(ans)

Solution (Python):
n=int(input())
mod=998244353
A=[]
for i in range(n):
  A.append(int(input()))
t=sum(A)
DP=[[0]*(t) for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  a=A[i]
  for j in range(t):
    DP[i+1][j]=(2*DP[i][j]+DP[i][max(0,j-a)])%mod

DP2=[[0]*(t) for _ in range(n+1)]
DP2[0][0]=1
for i in range(n):
  a=A[i]
  for j in range(t):
    if j>=a:
      DP2[i+1][j]=(DP2[i][j]+DP2[i][j-a])%mod
    else:
      DP2[i+1][j]=DP2[i][j]

ans=1
for i in range(n):
  ans=(ans*3)%mod
if t%2==1:
  print((ans-3*DP[n][t//2+1])%mod)
else:
  print((ans-3*DP[n][t//2]+3*DP2[n][t//2])%mod)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import numpy as np




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_num = sum(data)
    mod = 998244353

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    dp2 = np.zeros(sum_num + 1, dtype=np.int64)
    dp2[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp2
        dp2 = 1 * prev
        dp2[now_num:] += prev[:-now_num]
        dp2 %= mod

    ans = pow(3, num, mod)
    hikukazu = 0
    for i in range(math.ceil(sum_num / 2), sum_num + 1):
        hikukazu += dp[i]
    if sum_num % 2 == 0:
        hikukazu -= dp2[sum_num // 2]
    ans -= hikukazu * 3
    ans %= mod
    print(ans)
    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import numpy as np




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_num = sum(data)
    mod = 998244353

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    ans = pow(3, num, mod) - dp[(1 + sum_num) // 2:].sum() * 3
    if sum_num % 2 == 0:
        dp2 = np.zeros(sum_num + 1, dtype=np.int64)
        dp2[0] = 1
        for i in range(num):
            now_num = data[i]
            
            dp2[now_num:] += dp2.copy()[:-now_num]
            dp2 %= mod
        ans += dp2[sum_num // 2] * 3


    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

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




dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 
    dp[a:] += prev[:-a] 
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3

if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

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



dp = np.zeros(S//2+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev.copy()
    dp[a:] += prev[:-a] * 2
    dp %= MOD

answer = pow(3,N,MOD) - dp.sum() * 3
if S % 2 == 0:
    dp = np.zeros(S//2+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

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




dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 
    dp[a:] += prev[:-a] 
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3

if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

Solution (Python):
DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N = int(input())
INL = [II() for _ in range(N)]
SM = sum(INL)
HSM = SM//2

DP1 = [[0]*(SM+1) for _ in range(N+1)]
DP2 = [[0]*(SM+1) for _ in range(N+1)]
DP1[0][0] = 1
DP2[0][0] = 1

for i, value in enumerate(INL, 1):
    for j in range(SM+1):
        if j-value >= 0:
            DP1[i][j] = (2*DP1[i-1][j]+DP1[i-1][j-value])%DVSR
            DP2[i][j] = (DP2[i-1][j]+DP2[i-1][j-value])%DVSR
        else:
            DP1[i][j] = (2*DP1[i-1][j])%DVSR
            DP2[i][j] = DP2[i-1][j]

sub = 0
patall = POW(3, N)
for i in range(HSM+1, SM+1):
    sub += DP1[N][i]*3

if SM % 2 == 0:
    sub += 3*(DP1[N][HSM] - 2*DP2[N][HSM])
    sub += 3*DP2[N][HSM]



print((patall - sub) % DVSR)

Solution (Python):
DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N = int(input())
INL = [II() for _ in range(N)]
SM = sum(INL)
HSM = SM//2

DP1 = [[0]*(SM+1) for _ in range(N+1)]
DP2 = [[0]*(SM+1) for _ in range(N+1)]
DP1[0][0] = 1
DP2[0][0] = 1

for i in range(1,N+1):
    value = INL[i-1]
    for j in range(SM+1):
        if j-value >= 0:
            DP1[i][j] = (2*DP1[i-1][j]+DP1[i-1][j-value])%DVSR
            DP2[i][j] = (DP2[i-1][j]+DP2[i-1][j-value])%DVSR
        else:
            DP1[i][j] = (2*DP1[i-1][j])%DVSR
            DP2[i][j] = DP2[i-1][j]

sub = 0
patall = POW(3, N)
for i in range(HSM+1, SM+1):
    sub += DP1[N][i]*3

if SM % 2 == 0:
    sub += 3*(DP1[N][HSM] - 2*DP2[N][HSM])
    sub += 3*DP2[N][HSM]



print((patall - sub) % DVSR)

Solution (Python):
n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=(dp_1[i-1][j]+dp_1[i-1][j-a_list[i]])%mod
        else:
            dp[i][j]=dp[i-1][j]*2%mod
            dp_1[i][j]=dp_1[i-1][j]%mod
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=(Sum+dp[n][i]*3)%mod
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)

Solution (Python):
def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = [0]*(SUM+1)
    dp3 = [0]*(SUM+1)
    dp1[0]=1
    dp3[0]=1
    
    for n in range(N):
        a = As[n]
        dp1 = [(dp1[s]+(dp1[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]
        dp3 = [(dp3[s]*2 + (dp3[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]

    S3 = (sum(dp3[(SUM+1)//2:])*3)%DIV
    S1 = (dp1[(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())

Solution (Python):
from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = [0]*(SUM+1)
    dp3 = [0]*(SUM+1)
    dp1[0]=1
    dp3[0]=1
    
    for n in range(N):
        a = As[n]
        dp1 = [(dp1[s]+(dp1[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]
        dp3 = [(dp3[s]*2 + (dp3[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]

    S3 = (sum(dp3[(SUM+1)//2:])*3)%DIV
    S1 = (dp1[(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())

Solution (Python):
import numpy as np

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

M = 998244353
count_all = (3 ** N - 3 * (2 ** N - 2) - 3) % M

S = sum(numbers)
count3 = np.zeros((N, S + 1), dtype=np.int64)
count3[0, 0] = 2
count3[0, numbers[0]] = 1
count2 = np.zeros((N, S + 1), dtype=np.int64)
count2[0, 0] = 1
count2[0, numbers[0]] = 1

for i in range(1, N):
    count3[i, numbers[i]:] += count3[i - 1, :-numbers[i]]
    count3[i, :] += 2 * count3[i - 1, :]
    count3[i, :] %= M
    count2[i, numbers[i]:] += count2[i - 1, :-numbers[i]]
    count2[i, :] += count2[i - 1, :]
    count2[i, :] %= M

invalid_from = S // 2 + 1
if (S % 2 == 0):
  invalid_from = S // 2
count_invalid = np.sum(count3[N - 1, invalid_from:-1]) - 2 * np.sum(count2[N - 1, invalid_from:-1])
count_invalid %= M

print((count_all - 3 * count_invalid) % M)

Solution (Python):
MOD = 998244353

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

S = sum(A)
memo0 = [0] * (S+1)
memo1 = [0] * (S+1)
memo0[0] = 1
memo1[0] = 1



def dp0():
    for i in range(n):
        for s in range(S, A[i]-1, -1):
            memo0[s] = (memo0[s] + memo0[s-A[i]]*2) % MOD



def dp1():
    for i in range(n):
        for s in range(S, A[i]-1, -1):
            memo1[s] = (memo1[s] + memo1[s-A[i]]) % MOD


dp0()
dp1()

ans = pow(3, n, MOD)

for l in range(0, S//2+1):
    ans = (ans - memo0[l]*3) % MOD

if S % 2 == 0:
    ans = (ans + memo1[S//2]*3) % MOD


print(ans)