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

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>=0:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print([(z+e[s//2]*3)%M,z][s%2])

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>=0:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s+1>>1
while i<=s:z=(z-d[i]*3)%M;i+=1
print([(z+e[s//2]*3)%M,z][s%2])

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>=0:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
for i in range(s+1>>1,s+1):z=(z-d[i]*3)%M
print([(z+e[s//2]*3)%M,z][s%2])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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 numpy as np

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

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


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


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


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

Submission status: Accepted

Solution code:
import numpy as np

mod = 998244353


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


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

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

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate


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

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

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 numpy as np

mod = 998244353
N = int(input())
a = np.array([int(input()) for i in range(N)])
sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1), dtype=np.int64)
dp[0,0] = 1

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

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

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

print(res % mod)

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

print(int(res % mod))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

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


MOD = 998244353

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

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

# 1要素目: i番目の整数までを考慮
# 2要素目: [both>0, (緑or青)>0, both==0]
# 3要素目: 最大の色(赤とする)の和, sum_aの半分まで
dp = np.zeros((N+1, 3, 1 + (sum_a+1)//2), dtype=int)
dp[0, 2, 0] = 1

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

    # 赤に入れる
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    # 緑or青に入れる
    dp[i, 0, :] += (dp[i-1, 0, :] + dp[i-1, 1, :]) * 2
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 2, :]

    dp[i, :, :] %= MOD

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)
# import time

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


MOD = 998244353

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

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

# 1要素目: i番目の整数までを考慮
# 2要素目: [both>0, 緑>0&青==0, 緑==0&青>0, both==0]
# 3要素目: 最大の色(赤とする)の和
dp = np.zeros((N+1, 3, 1 + (sum_a+1)//2), dtype=int)
dp[0, 2, 0] = 1

for i in range(1, N+1):
    # 赤に入れる
    a = a_list[i-1]
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    # 緑or青に入れる
    dp[i, 0, :] += (dp[i-1, 0, :] + dp[i-1, 1, :]) * 2
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 2, :]

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

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

Submission status: Accepted

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

#dp[i番目まで選ぶ][Aの長さ]= 通り数(B,Cの選び方も考慮する)
dp = [[0]*(sum_len+1) for i in range(n+1)]
dp[0][0]= 1
for i in range(n):
    for len in range(sum_len+1):
        #a[i]を選ばないとき → a[i]はBかCに振り分けられるので*2をする
        dp[i+1][len] = dp[i][len]*2
        #a[i]を選ぶとき
        if 0 <= len-a[i]:
            dp[i+1][len] += dp[i][len-a[i]]
        dp[i+1][len] %= MOD

            
#dp[i番目まで選ぶ][Aの長さ]= 通り数(B,Cの選び方を考慮しない)
dp2 = [[0]*(sum_len+1) for i in range(n+1)]
dp2[0][0]= 1
for i in range(n):
    for len in range(sum_len+1):
        #a[i]を選ばないとき
        dp2[i+1][len] = dp2[i][len]
        #a[i]を選ぶとき
        if 0 <= len-a[i]:
            dp2[i+1][len] += dp2[i][len-a[i]]
        dp2[i+1][len] %= MOD

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

Submission status: Accepted

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

sum_A = sum(A)
MOD = 998244353

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

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


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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

sum_A = sum(A)
MOD = 998244353

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

for a in A:
    tmp_sum += a
    for i in reversed(range(tmp_sum + 1)):
        if i - a >= 0:
            # R に塗れる場合
            dp1[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1[i] = (dp1[i] * 2) % MOD
            dp2[i] = dp2[i]


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

Submission status: Accepted

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

sum_A = sum(A)
MOD = 998244353

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


for a in A:
    for i in reversed(range(sum_A + 1)):
        if i - a >= 0:
            # R に塗れる場合
            dp1[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1[i] = (dp1[i] * 2) % MOD
            dp2[i] = dp2[i]


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

Submission status: Accepted

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

S = sum(A)

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

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

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


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

print(ans % MOD)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

sum_A = sum(A)
MOD = 998244353

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


for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        if i - a >= 0:
            # R に塗れる場合
            dp1_[i] = (dp1[i - a] + dp1[i] * 2) % MOD
            dp2_[i] = (dp2[i - a] + dp2[i]) % MOD
        else:
            dp1_[i] = (dp1[i] * 2) % MOD
            dp2_[i] = dp2[i]
    dp1, dp2 = dp1_, dp2_


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

Submission status: Accepted

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

sum_A = sum(A)
MOD = 998244353

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

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        # R に塗った場合
        if i + a <= sum_A:
            dp1_[i + a] = (dp1_[i + a] + dp1[i]) % MOD
            dp2_[i + a] = (dp2_[i + a] + dp2[i]) % MOD
        # G, B に塗った場合
        dp1_[i] = (dp1_[i] + dp1[i] * 2) % MOD
        dp2_[i] = (dp2_[i] + dp2[i]) % MOD
    dp1 = dp1_
    dp2 = dp2_

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for i in range(n)]
w = sum(a)
mod =998244353

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

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

#sより大きいのはブー
s = w//2+1
if w %2 == 0:
    d = [[0]*(s+1) for i in range(n)]
    d[0][0] = 1
    d[0][a[0]] = 1
    cnt = a[0]

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

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

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

Submission status: Accepted

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

L = 90001
LARGE = 998244353

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

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

Submission status: Accepted

Solution code:
N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る
 
aaa = [int(input()) for _ in range(N)]
 
sum_now = 0
DP = [[0] * (sum(aaa)+1) for i in range(N)]
DP2 = [[0] * (sum(aaa)+1) for i in range(N)]
 
a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1
 
DP2[0][0] = 1
DP2[0][a] = 1
 
sum_now += a
 
for i in range(1, N):
	a = aaa[i]
	for j in range(sum_now + 1):
		DP[i][j] += DP[i-1][j] * 2
		DP[i][j] %= mod
		DP[i][j + a] += DP[i-1][j]
 
		DP2[i][j] += DP2[i-1][j]
		DP2[i][j] %= mod
		DP2[i][j + a] += DP2[i-1][j]
 
	sum_now += a
 
# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum(aaa) %2 == 0):
	num_too_long -= DP2[N-1][int(sum(aaa) /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )

Submission status: Accepted

Solution code:
N = int(input())
A = [abs(int(input())) for _ in range(N)]
#A.sort()
s = sum(A)

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

mod = 998244353

dp = [[0]*(s+1) for _ in range(N)]
# dp[n][s] An-1(0-index)まで加えて、Rの和がsになるのが何通りか（残りのG,Bまで含めて）
dp[0][0] = 2
dp[0][A[0]] = 1
temp_sum = A[0]

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


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

  #DP
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: #i+1番目の数字a[i]を足せるかも
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

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



print(answer)

Submission status: Runtime Error

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(2/0)
  print((ans+dp2[-1][sm//2]//2*6)%mod)

Submission status: Runtime Error

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 range 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: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N+1)]


def factorize(n):
    b = 2
    fct = {}
    while b * b <= n:
        while n % b == 0:
            n //= b
            if b in fct.keys():
                fct[b] += 1
            else:
                fct[b] = 1
        b += 1
    if n > 1:
        fct[n] = 1
    return fct


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


g = abs(A[0])
for a in A:
    g = gcd(g, abs(a))
cand = list(factorize(g).keys())
ans_set = [c for c in cand]


def SieveofEratosthenes(N: int) -> list:
    isPrime = [0] + [1 for _ in range(N-1)]
    numList = [i+1 for i in range(N)]
    for i in range(1, N):
        if isPrime[i] == 1:
            for k in range(i+1, N):
                if (k+1) % (i+1) == 0:
                    isPrime[k] = 0
    returnList = []
    for i, v in enumerate(isPrime):
        if v == 1:
            returnList.append(numList[i])
    return returnList


cand = SieveofEratosthenes(N+1)


def ans(cand):
    for p in cand:
        if A[0] % p != 0:
            continue
        for n in range(1, p):
            cur = 0
            for k in range((N-n)//(p-1)+1):
                cur += A[n+k*(p-1)]
                cur %= p
            if cur != 0:
                break
        if cur == 0:
            ans_set.append(p)
    return ans_set


A.reverse()
ans_set = ans(cand)
ans = list(set(ans_set))
for p in ans:
    print(p)

Submission status: Runtime Error

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 i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

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

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色で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] * 2
            else:
                dp[i][length] = dp[i-1][length]*2
            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]
            while (DP2[i][j] > mod):
                DP2[i][j] -= mod
            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: Runtime Error

Solution code:
N=int(input())
a=[int(input()) for i in range(N)].sort()
su=sum(a)
#すべての組み合わせのリストと可能な三角形の集合を作り、前者の要素のうち後者にある物の数を返す。

bool_list=[]
A,B,C=0,0,0

#i項目を選んだかどうかで再帰する関数
def saiki(i,A,B,C):
    if judge(A,B,C)!=True:
        return
    if i==N:
        bool_list.append(True)
        return
    suuchi=a[i]
    saiki(i+1,A+suuchi,B,C)
    saiki(i+1,A,B+suuchi,C)
    saiki(i+1,A,B,C+suuchi)

#与えられた3つの数について三角不等式を満たすかboolを返す

def judge(n,m,l):
    if n>=su:
        return False
    if m>=su:
        return False
    if l>=su:
        return False
    return True

saiki(0,A,B,C)

print(bool_list.count(True)%998244353)

Submission status: Runtime Error

Solution code:
M,z,s=998244353,1,0
N,*A=map(int,open(0))
d=[1]+[0]*7**6
e=d.copy()
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: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())

total = 0
A = []
for i in range(N):
    a = int(input())
    total += a
    A.append(a)

mod = 998244353

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

exc = 0
for j in range((total+1)//2, total+1):
    exc += dp[N][j]
    exc %= mod

res = (3**N % mod) - exc * 3

if total % 2 == 0:
    dp = [[0]*91000 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(300*i, -1, -1):
            dp[i][j+A[i-1]] += dp[i-1][j]
            dp[i][j+A[i-1]] %= mod
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
    res += dp[N][total/2] * 3

print(res % mod)

Submission status: Runtime Error

Solution code:
N = int(input())

total = 0
A = []
for i in range(N):
    a = int(input())
    total += a
    A.append(a)

mod = 998244353

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

exc = 0
for j in range((total+1)//2, total+1):
    exc += dp[N][j]
    exc %= mod

res = (3**N % mod) - exc * 3

if total % 2 == 0:
    dp = [[0]*91000]*(N+1)
    for i in range(1, N+1):
        for j in range(300*i, 0, -1):
            dp[i][j+A[i-1]] += dp[i-1][j]
            dp[i][j+A[i-1]] %= mod
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
    res += dp[N][total/2] * 3

print(res % mod)

Submission status: Runtime Error

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
from collections import Counter

DPLIST=[[0]*301 for i in range(MAX+2)]
DPLIST[0][0]=1
ANS=0

for k in range(N):
    for i in range(k+1,-1,-1):
        for j in range(MAX+1,-1,-1):
            DPLIST[min(j+A[k],MAX+1)][i+1]+=DPLIST[j][i]

ANS=(pow(3,N,mod)-3*pow(2,N,mod))%mod
MINUS=0

for i in range(N-1):
    MINUS+=3*(pow(2,(N-i),mod)-2)*DPLIST[MAX+1][i]

print((ANS-MINUS+3)%mod)

Submission status: Runtime Error

Solution code:
N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

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

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

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

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

sum_now += a

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

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

	sum_now += a

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