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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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
#print(dp)
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
    
#print(dp)
#print(dp2)

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

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

Submission status: Accepted

Solution code:
MOD = 998244353
def pow(n,k,m):#n^k mod 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[x]:Bの和=xとなるような塗り方の総数

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)

Submission status: Accepted

Solution code:
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):
    #print(dp)
    a_i = a[i-1]
    dp[i,a_i:] += dp[i-1,:-a_i]
    #print(dp[i,:])
    #print("========")
    dp[i,:] += dp[i-1,:]*2
    dp[i,:] %= MOD
#print(dp)
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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): # length of
    s = xs[i]
    curtotal += s
    dp[i] = (dp[i-1] * 2)
    dp[i][s:] += dp[i-1][:-s]
    dp[i] %= MOD

#print(dp)

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]

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


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

Submission status: Accepted

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

# R=G=S/2, B=0
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
# print(DP)
# print(DP2)

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)

Submission status: Accepted

Solution code:

def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    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[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            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
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

# D1[i][r]: i個塗った時点でR=rとなる場合の数
D1 = np.zeros((N+1, S+1), dtype=int)
D1[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
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)

Submission status: Accepted

Solution code:
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[i][r]: i個塗った時点でR=rとなる場合の数
D1 = np.zeros((N+1, S+1), dtype=int)
D1[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
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)

Submission status: Accepted

Solution code:
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[i][r]: i個塗った時点でR=rとなる場合の数
D1 = np.zeros((N+1, S+1), dtype=int)
D1[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
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)

Submission status: Accepted

Solution code:
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
#     pow = [a]
#     while 1 << i <= n:
#         pow.append(pow[-1] * pow[-1] % mod)
#         i += 1
#     for j in range(i):


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

# D1[i][r]: i個塗った時点でR=rとなる場合の数
D1 = np.zeros((N+1, S+1), dtype=int)
D1[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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=[[0 for _ in range(ASum+1)] for _ in range(2)]
dp=np.zeros((2,ASum+1),dtype=np.int64)
dp[0][0] = 2
dp[0][A[0]] = 1

# dpOther=[[0 for _ in range(ASum+1)] for _ in range(2)]
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 in range(1,N):
for n, a in enumerate(A):
	if n==0:
		continue
	# curMax += a
	current = n % 2
	prev = (n+1) % 2
	# for e in range(curMax+1):
	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:
	# 合計が奇数の場合、ceil
	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 )

Submission status: Accepted

Solution code:
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=[[0 for _ in range(ASum+1)] for _ in range(2)]
dp=np.zeros((2,ASum+1),dtype=np.int64)
dp[0][0] = 2
dp[0][A[0]] = 1

# dpOther=[[0 for _ in range(ASum+1)] for _ in range(2)]
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 in range(1,N):
for n, a in enumerate(A):
	if n==0:
		continue
	# curMax += a
	current = n % 2
	prev = (n+1) % 2
	# for e in range(curMax+1):
	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:
	# 合計が奇数の場合、ceil
	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 )

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=np.sum(A)

# dp=[[0 for _ in range(ASum+1)] for _ in range(2)]
dp=np.zeros((2,ASum+1),dtype=np.int64)
dp[0][0] = 2
dp[0][A[0]] = 1

# dpOther=[[0 for _ in range(ASum+1)] for _ in range(2)]
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 in range(1,N):
for n, a in enumerate(A):
	if n==0:
		continue
	# curMax += a
	current = n % 2
	prev = (n+1) % 2
	# for e in range(curMax+1):
	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:
	# 合計が奇数の場合、ceil
	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 )

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/tenka1-2019/submissions/5065329

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)  # 三角形を構成できない場合を含むRGBの組み合わせ総数

'''(2)単円'''
dp = [[0] * (total + 1) for _ in range(N + 1)]
dp[0][0] = 1
# dp[i][R]:=i番目まででRとなる場合の数

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
        # g, bに加算する分で、2回起こる
# print(dp)

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

'''(3)２円の積集合'''
if total % 2 == 0:
    dp2 = [[0] * (total + 1) for _ in range(N + 1)]
    dp2[0][0] = 1
    # dp[i][R]:=i番目まででRとなる場合の数

    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
    # print(dp2)

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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil

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

MOD = 998244353


S = sum(A)
# 赤色の整数の和がiとなるような塗り方の個数
dp = [0 for _ in range(S + 1)]
dp[0] = 1
# 赤色の整数の和がi, 他の整数がすべて青色となるような塗り方の個数
dp2 = [0 for _ in range(S // 2 + 1)]
dp2[0] = 1

# 動的計画法により、dp, dp2を求める
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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