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



Sample input:
4
1
1
1
2


Sample output:
18

Submission status: Accepted

Solution code:
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)
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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]
            # prev = dp2
            dp2[now_num:] += dp2.copy()[:-now_num]
            dp2 %= mod
        ans += dp2[sum_num // 2] * 3


    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

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
# 2色が反例となる場合を引きすぎている
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)

Submission status: Accepted

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

# 赤青の和がS/2以下となるものを求めて3倍

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)

Submission status: Accepted

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

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

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
# 2色が反例となる場合を引きすぎている
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)

Submission status: Accepted

Solution code:
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(DP2[N])
# print(SM)
print((patall - sub) % DVSR)

Submission status: Accepted

Solution code:
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(DP2[N])
# print(SM)
print((patall - sub) % DVSR)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
a = [int(input()) for _ in range(N)]
mod = 998244353
suma = sum(a)
memo = np.zeros((N+1, suma+1), dtype=np.int)
memo[0][0] = 1
memoe = np.zeros((N+1, suma+1), dtype=np.int)
memoe[0][0] = 1

ttl = 3
for i in range(N-1):
  ttl *=3
  ttl %= mod

for i in range(1, N+1):
  memotmp = memo[i-1]
  memotmpe = memoe[i-1]
  memotmp = np.concatenate((np.zeros((a[i-1]), dtype=np.int), memotmp),axis=1)
  memotmpe = np.concatenate((np.zeros((a[i-1]), dtype=np.int), memotmpe),axis=1)
  memo[i] = (memo[i-1]*2 + memotmp[:suma+1])%mod
  memoe[i] = (memoe[i-1] + memotmpe[:suma+1])%mod

ans = sum(memo[N][(suma-1)//2+1:])
if suma%2==0:
  ans -= memoe[N][suma/2]
  
print(((ttl - ans*3)%mod+mod)%mod)

Submission status: Accepted

Solution code:
def d_three_colors(N, A, MOD=998244353):
    # 参考: http://smijake3.hatenablog.com/entry/2019/04/21/023359
    a_sum = sum(A)

    # dp0[i][s]: a_iまでの数を使い、G+Bの値がsとなるような選び方
    # としてDPを行うが、iを0から増やすのではなくa_sumから減らすやり方だと、
    # iについて配列を保持しておく必要がなくなり、1次元配列で済む
    dp0 = [0] * (a_sum + 1)
    dp0[0] = 1
    for a in A:
        for s in range(a_sum, a - 1, -1):
            # a_iを採用する場合、Gに足す場合とBに足す場合の2通りあるので、
            # dp[s-a]の2倍を足すことになる
            dp0[s] = (dp0[s] + 2 * dp0[s - a]) % MOD

    # dp[s]: GとBにa_iの値を平等に割り振って、G+Bの値がsとなるような選び方
    dp1 = [0] * (a_sum + 1)
    dp1[0] = 1
    for a in A:
        for s in range(a_sum, a - 1, -1):
            # a_iを採用する場合、GとBに平等に足すことになる(dp0のループと違い、
            # どちらに足すかを選ばない)ので、dp1[s-a]の1倍を足すことになる
            dp1[s] = (dp1[s] + dp1[s - a]) % MOD

    ans = pow(3, N, MOD)  # すべての塗り方
    for l in range(a_sum // 2 + 1):
        # G+B<=a_sum//2 のとき、三角形は存在しないので、その分を引く
        ans = (ans - 3 * dp0[l]) % MOD
    if a_sum % 2 == 0:
        # このとき、G==B==a_sum//2の場合の数を引きすぎているので、足す
        ans = (ans + 3 * dp1[a_sum // 2]) % MOD
    return ans

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
m = 998244353
S = a.sum()

# 最初のt個の整数を塗り分け, Rの整数の和がrであるような場合の数
DP_A = np.zeros((N+1, S+1), dtype=np.int64)
# 最初のt個の整数を塗り分け, Rの整数の和がrで, Bの和が0であるような場合の数
DP_B = np.zeros((N+1, S+1), dtype=np.int64)

DP_A[0, 0] = 1
DP_B[0, 0] = 1

# for t in range(N):
#     for r in range(S + 1):
#         # t + 1番目の整数をRにしない -> G or Bにする
#         DP_A[t+1, r] = DP_A[t, r] * 2 % m
#         # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
#         if r - a[t] >= 0:
#             DP_A[t+1, r] += DP_A[t, r - a[t]] % m
#         # t+1 番目の整数をRにしない -> Gを加える
#         DP_B[t+1, r] = DP_B[t, r] % m
#         # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
#         if r - a[t] >= 0:
#             DP_B[t+1, r] += DP_B[t, r - a[t]] % m

for t in range(N):
    DP_A[t+1, :] = (DP_A[t, :]) * 2 % m
    DP_A[t+1, a[t]:] += DP_A[t, :-a[t]] % m
    DP_B[t+1, :] = (DP_B[t, :]) % m
    DP_B[t+1, a[t]:] += DP_B[t, :-a[t]] % m

res1 = DP_A[N, int(np.ceil(S/2)):].sum()
res2 = DP_B[N, int(np.ceil(S/2))] if S % 2 == 0 else 0
res = (3 ** N - res1 * 3 + res2 * 3) % m
print(res)

Submission status: Accepted

Solution code:
N = int(input())
alist = [int(input()) for i in range(N)]
import numpy as np
### 三角形が成立しない場合を数える
alist.sort(reverse=False) #大きい方からチェックするとS/2に早く到達しやすい
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
dptableA[N, int(np.ceil(Sharf)):] = 1
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
if S %2 == 0:
    dptableB[N, int(Sharf)] = 1 

#dpの計算をまとめて行う
for i in range(N, 0, -1): #後ろから見ていく
    n = i - 1
    an = alist[n]
    asn = asum[n]
    dptableA[n, 0:asn+1] = (2*dptableA[n+1, 0:asn+1] + dptableA[n+1, an:an+asn+1])%MOD
    #dptableA[n] = [(2*dptableA[n+1][k]+dptableA[n+1][k+alist[n]]) % MOD for k in range(asum[n]+1)]
    dptableB[n, 0:asn+1] = (dptableB[n+1, 0:asn+1] + dptableB[n+1, an:an+asn+1])%MOD
    #dptableB[n] = [(dptableB[n+1][k]+dptableB[n+1][k+alist[n]]) %MOD for k in range(asum[n]+1)]
retA, retB = dptableA[0,0], dptableB[0,0]
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline
N=int(input())
A = [int(input()) for i in range(N)]
mod = 998244353

S = sum(A)
maxA = max(A)
dp = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
dp[0][S-math.ceil(S/2)]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = (dp[i-1][j+A[i-1]]*2 + dp[i-1][j])%mod
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
  dp2[0][S-math.ceil(S/2)]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = (dp2[i-1][j+A[i-1]] + dp2[i-1][j])%mod
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%mod)

Submission status: Accepted

Solution code:
import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)])
TOTAL=pow(3,N,MOD)
ASum=sum(A)
sumEnd=0
sumEnd=ASum//2+1

dp=np.array([0 for _ in range(sumEnd)],dtype=np.int64)
dp[0] = 1

for n in range(N):
	dp[A[n]:] += dp[:-A[n]]*2 % MOD

plus = 0
if ASum % 2 == 0:
	# 合計が偶数
	dpOther=np.array([0 for _ in range(sumEnd+1)],dtype=np.int64)
	dpOther[0] = 1
	for n in range(N):
		dpOther[A[n]:] += dpOther[:-A[n]] % MOD
	plus = (dpOther[ASum//2]*3) % MOD

exceptCnt=0
for s in range(0,sumEnd):
	exceptCnt = (exceptCnt + dp[s]*3) % MOD

exceptCnt -= plus
print((TOTAL - exceptCnt) % MOD )

Submission status: Accepted

Solution code:
import math
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)
m = 998244353
dp1 = np.zeros((N+1, s+1), dtype=np.int64)
dp1[0, 0] = 1
dp2 = np.zeros((N+1, s//2+1), dtype=np.int64)
dp2[0, 0] = 1
for i, ai in enumerate(a):
    dp1[i+1, :]   += dp1[i, :] * 2 % m
    dp1[i+1, ai:] += dp1[i, :-ai]
    dp2[i+1, :]   += dp2[i, :] % m
    dp2[i+1, ai:] += dp2[i, :-ai]
subset1 = np.sum(dp1[N, math.ceil(s/2):])
subset2 = 0 if s % 2 == 1 else dp2[N, s//2]
print((3 ** N - 3 * subset1 + 3 * subset2) % m)

Submission status: Accepted

Solution code:
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    MOD = 998244353

    S = sum(A)
    a = A[0]
    # dp0[i][j]: DP table
    #            the number of combinations that the one side length is j 
    #            until using the i-th A[i].
    dp0 = np.zeros((N, S+1), dtype=np.int64)
    dp0[0, a] = 1
    dp0[0, 0] = 2

    # dp1[i][j]: DP table
    #            the number of one side length is j and the other one is 0
    #            until using the i-th A{i].
    dp1 = np.zeros((N, S+1), dtype=np.int64)
    dp1[0, a] = 1
    dp1[0, 0] = 1
    for i in range(1, N):
        a = A[i]

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

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


    ng = 0
    if S % 2 == 1:
        ng = np.sum(dp0[N-1, S//2 + 1:])
        ng = (ng * 3) % MOD

    else:
        ng = np.sum(dp0[N-1, S//2:])
        ng = (ng * 3 - dp1[N-1][S//2] * 3) % MOD

    ans = (pow(3, N, MOD) - ng) % MOD
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")
MOD = 998244353  # type: int


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def solve(N: int, a: "List[int]"):

    S = sum(a)
    # dp = [defaultdict(int) for _ in range(N)]
    dp = [[0]*(S+1) for _ in range(N)]
    # dp2 = [defaultdict(int) for _ in range(N)]
    dp2 = [[0]*(S+1) for _ in range(N)]
    dp[0][0] = 2
    dp[0][a[0]] = 1
    dp2[0][0] = 1
    dp2[0][a[0]] = 1
    for i in range(1, N):     # i+1番目の数字まで使ったとき
        # for key in dp[i-1]:
        for key in range(S+1):
            dp[i][key] = 2*dp[i-1][key]+dp[i-1][key-a[i]]
            dp[i][key] %= MOD
            dp2[i][key] = dp2[i-1][key] + dp2[i-1][key-a[i]]
            dp2[i][key] %= MOD

    # ans = power(3, N) - sum([dp[N-1][i] for i in range(-(-S//2), S+1)])*3
    ans = power(3, N) - sum(dp[N-1][-(-S//2):])*3
    ans %= MOD
    if S % 2 == 0:              #
        ans += 3*dp2[N-1][-(-S//2)]
        ans %= MOD
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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[i][j]: number of ways to obtain sum j for one of colors using first i integers.
# i = 0, 1, ..., N
# j = 0, 1, ..., S
dp0 = np.zeros((N + 1, S + 1), dtype=np.int64)

# dp1[i][j]: number of ways to obtain sum j for one of colors using first i integers,
#     but this time we use only TWO colors.
#     This will be used to find the number of cases when
#         (sum of R)= (sum of G) = S/2 & (sum of B) = 0 

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

# using 0 integer to obtain sum=0
dp0[0, 0] = 1
dp1[0, 0] = 1


for i, x in enumerate(A):

    # If we do not use the next integer x, e.g. not for R, the sum of R is same, but possible ways are doubled
    #     because x can be used for either G or B
    dp0[i+1, :] += dp0[i, :] * 2 % MOD

    # Then we update the case when we use the next integer x.
    #     Lets say, sum=p was obtained for 4 different ways without using current integer x,
    #     then sum=p+x can also be obtained for 4 different ways.
    dp0[i+1, x:] += dp0[i, :-x]

    # If we do not use the next integer x, e.g. not for R, the sum of R is same, and possible ways are the same
    #     because this time we use only TWO colors. (say R and G, we dont use x for R, then automatically x goes for G)
    dp1[i+1, :] += dp1[i, :] % MOD

    # Then we update the case when we use the next integer x.
    dp1[i+1, x:] += dp1[i, :-x]


# count cases: (R >= S / 2)
not_satisfy = np.sum(dp0[N][math.ceil(S/2):])

# count cases: (R = S / 2) & (B = S / 2)
double_reduct = 0 if S % 2 == 1 else dp1[N][S/2]

# total cases = 3 ** N

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

Submission status: Accepted

Solution code:
import math

n = int(input())
a = [0]
mod = 998244353
p = pow(3, n, mod)

for i in range(0, n):
    a.append(int(input()))

s = sum(a)
hs = math.ceil(s / 2)
dp = [[0 for j in range(0, s + 1)] for i in range(0, n + 1)]
dp[0][0] = 1

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

p = (p - 3 * sum(dp[n][hs:])) % mod

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

    p = (p + 3 * dp[n][hs]) % mod

print(p)

Submission status: Accepted

Solution code:
import math
import numpy as np

N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)

dp0 = np.zeros((N + 1, s + 1), dtype=np.int64)
dp0[0, 0] = 1
dp1 = np.zeros((N + 1, s // 2 + 1), dtype=np.int64)
dp1[0, 0] = 1

mod = 998244353
for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2 % mod
    dp0[i + 1, x:] += dp0[i, :-x] % mod
    dp1[i + 1, :] += dp1[i, :] % mod
    dp1[i + 1, x:] += dp1[i, :-x] % mod

# Counts of (R >= s / 2)
c0 = int(np.sum(dp0[N][math.ceil(s / 2):]))
# Counts of (R == s / 2 and G == s / 2)
c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

ans = (3 ** N - 3 * c0 + 3 * c1) % mod
print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np

N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)

# Counts of (R >= s / 2)
dp0 = np.zeros((N + 1, s + 1))
dp0[0, 0] = 1
# Counts of (R == s / 2 and G == s / 2)
dp1 = np.zeros((N + 1, s // 2 + 1))
dp1[0, 0] = 1

mod = 998244353
for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2 % mod
    dp0[i + 1, x:] += dp0[i, :-x] % mod
    dp1[i + 1, :] += dp1[i, :] % mod
    dp1[i + 1, x:] += dp1[i, :-x] % mod

c0 = int(np.sum(dp0[N][math.ceil(s / 2):]))
c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

ans = (3 ** N - 3 * c0 + 3 * c1) % mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env 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)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

N = INT()
a = np.array([INT() for _ in range(N)])

sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
dp[0][0] = 1

dp2 = np.zeros((N+1, sum_a//2+1))
dp2[0][0] = 1

for i, x in enumerate(a):
	dp[i+1, :] += dp[i, :]*2 % mod # 赤以外に塗り分ける
	dp[i+1, x:] += dp[i, :-x] % mod # 赤に塗り分ける
	dp2[i+1,:] += dp2[i, :] % mod
	dp2[i+1, x:] += dp2[i, :-x] % mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2:])+3*dp2[N,sum_a//2])%mod))
else:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2+1:]))%mod))

Submission status: Accepted

Solution code:
import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)

Submission status: Accepted

Solution code:
N = int(input())
a = [int(input()) for _ in range(N)]

s = sum(a)
mod = 998244353

dp1 = [0] * (s+1)
dp2 = [0] * (s+1)
dp1[0] = 1
dp2[0] = 1
sum_ = 0


ans = 0
for n in range(N):
    for i in reversed(range(sum_+1)):
        dp1[i] %= mod
        dp2[i] %= mod
        dp1[i+a[n]] += dp1[i]
        dp1[i] <<= 1
        dp2[i+a[n]] += dp2[i]
    #print(dp1,dp2)
    sum_ += a[n]

ans = (3 ** N)%mod
for i in range(s+1):
    if i*2 >= s:
        ans -= dp1[i]*3 + mod*3
        ans %= mod
    if i*2 == s:
        ans += dp2[i]*3
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
def solve():
    mod=998244353
    N=int(input())
    A=[]
    for i in range(N):
        A.append(int(input()))
    sumA=sum(A)
    sumA2=(sumA+1)//2

    dp = [[0]*(sumA2+2) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in range(sumA2+1):
            if dp[i][j]!=0:
                dp[i+1][j]=(dp[i+1][j]+dp[i][j]*2)%mod
                j2=min(sumA2,j+A[i])
                dp[i+1][j2]=(dp[i+1][j2]+dp[i][j])%mod
    ans=1
    for i in range(N):
        ans=(ans*3)%mod
    ans=(ans+mod-3*dp[N][sumA2])%mod

    if sumA%2==0:
        dp = [[0]*(sumA2+2) for i in range(N+1)]
        dp[0][0]=1
        for i in range(N):
            for j in range(sumA2+2):
                if dp[i][j]!=0:
                    dp[i+1][j]+=dp[i][j]
                    j2=min(sumA2+1,j+A[i])
                    dp[i+1][j2]+=dp[i][j]
        ans=(ans+3*dp[N][sumA2])%mod

    return ans

print(solve())

Submission status: Accepted

Solution code:
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] = 1
half_dp[0][0] = 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 
bigger_than_half = np.sum(dp[N][half_sum_a:])
half_half = half_dp[N][half_sum_a] if sum_a%2==0 else 0
ans = int(all_combination - 3* bigger_than_half + 3* half_half)%MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a_sum = sum(a)
half = int(a_sum / 2)

dp = [[0] * (a_sum + 1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    ni = i+1
    for j in range(a_sum+1):
        if dp[i][j] != 0:
            dp[ni][j] += (dp[i][j] * 2) % MOD
            dp[ni][j+a[i]] += dp[i][j]
ans = pow(3, n, MOD)
for item in dp[n][half:]:
    ans -= item * 3
    ans %= MOD

if a_sum % 2 == 0:
    dp = [[0] * (half + 1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        ni = i+1
        for j in range(half+1):
            dp[ni][j] += dp[i][j] % MOD
            if j+a[i] < half+1:
                dp[ni][j+a[i]] += dp[i][j] % MOD
ans += dp[n][half] * 3
ans %= MOD
if ans < 0:
    ans += MOD
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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)
assert s%2==1
l = s//2 + int(s%2==1)
# dp = [[0]*(s+1) for _ in range(n+1)]
dp = [0]*(s+1)
dp[0] = pow(2, n, M)
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
# if s%2==0:
#     dp[s//2] //= 2
val = sum(dp[i] for i in range(l, s+1)) * 3
ans = (pow(3,n,M) - val)%M
print(ans%M)

Submission status: Runtime Error

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