Problem:


Score : 1000 points

Problem Statement

We will host a rock-paper-scissors tournament with N people. The participants are called Person 1, Person 2, \ldots, Person N.
For any two participants, the result of the match between them is determined in advance.
This information is represented by positive integers A_{i,j} ( 1 \leq j < i \leq N ) as follows:

If A_{i,j} = 0, Person j defeats Person i.

If A_{i,j} = 1, Person i defeats Person j.

The tournament proceeds as follows:

We will arrange the N participants in a row, in the order Person 1, Person 2, \ldots, Person N from left to right.

We will randomly choose two consecutive persons in the row. They will play a match against each other, and we will remove the loser from the row.
We will repeat this process N-1 times, and the last person remaining will be declared the champion.

Find the number of persons with the possibility of becoming the champion.

Constraints

1 \leq N \leq 2000

A_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
A_{2,1}
A_{3,1}A_{3,2}
:
A_{N,1}\ldotsA_{N,N-1}

Output

Print the number of persons with the possibility of becoming the champion.

Sample Input 1

3
0
10

Sample Output 1

2

Person 1 defeats Person 2, Person 2 defeats Person 3 and Person 3 defeats Person 1.
If Person 1 and Person 2 play the first match, Person 3 will become the champion.
If Person 2 and Person 3 play the first match, Person 1 will become the champion.

Sample Input 2

6
0
11
111
1111
11001

Sample Output 2

3



Sample input:
3
0
10


Sample output:
2

Submission status: Wrong Answer

Solution code:
#人i が 人j に勝つならTrue
def judge(rule, i, j):
  rev = False
  if i < j:
    i, j = j, i
    rev = True
  if rule[i - 1][j] == 0:
    ret = False
  else:
    ret = True
  
  if rev:
    ret = not ret
    
  return ret


n = int(input())
rule = [list(map(lambda x:int(x), list(input()))) for i in range(n - 1)]
#print(rule)
for i in range(n):
  for j in range(n):
    if i != j:
      vic = judge(rule, i, j)
#      print("{}x{}:{}".format(i, j, vic))    
      
left = [0]
for i in range(1,n):
  for j in left:
    if judge(rule, i, j):
      left.append(i)
      break
#print(left)
right = [n - 1]
for i in range(n - 2, -1, -1):
  #print(i)
  for j in right:
    if judge(rule, i, j):
      right.append(i)
      break
#print(right)

result = set(left).intersection(set(right))

print(len(result))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(1000000)

n = int(input())
people = [i for i in range(n)]
a = [[-1] * n for _ in range(n)]
for i in range(n-1):
    ai = input()
    for j, aij in enumerate(ai):
        a[i+1][j] = int(aij)
        a[j][i+1] = (int(aij) + 1) % 2

memo = {}

# startからendの範囲で優勝の可能性があるやつ
def solve(start, end):
    key = (start, end)
    if key in memo:
        return memo[key]
    if start == end:
        return [start]
    elif start + 1 == end:
        if a[start][end] == 1:
            return [start]
        else:
            return [end]
    winable = set()

    # 全勝の存在をチェック
    for i in range(start, end):
        if sum(a[i]) == end - start + 1 - 2:
            return [i]
    for i in range(start+1, end+1):
        left_winable = solve(start, i-1)
        if (start, i-1) not in memo:
            memo[(start, i-1)] = left_winable
        right_winable = solve(i, end)
        if (i, end) not in memo:
            memo[(i, end)] = right_winable
        for l in left_winable:
            for r in right_winable:
                if a[l][r] == 1:
                    winable.add(l)
                else:
                    winable.add(r)
    return list(winable)


def main():
    winable = solve(0, n-1)
    print(len(winable))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))



N = int_raw()
As =[input() for _ in range(N-1)]

def main():
    ans =0 
    for j in range(N):
        is_p = j==0
        for i in range(j):
            if As[j-1][i] =="1":
                is_p = True
        is_b = j == (N-2)
        for k in range(j+1,N):
            if As[k-1][j] =="0":
                is_b = True
        if is_b and is_p:
            ans+=1
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())

a_table = [[]]

for i in range(N - 1):
	a_table.append([x == "1" for x in input().strip()])

for i in range(N):
	a_list = a_table[i]
	a_list.append(None)
	for j in range(i + 1, N):
		a_list.append(a_table[j][i])

def check(x):
	stack = [x]
	visited = {x}
	a_list = a_table[x]
	while stack:
		cur = stack.pop()
		for i in range(N):
			if i != cur and a_list[i] and not i in visited:
				stack.append(i)
				visited.add(i)
	return len(visited) == N - 1

count = 0
for i in range(N):
	if check(i):
		count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(input()) for i in range(n-1)]
ct=0
for i in range(n-1):
  for j in range(i+1):
    if l[i][j]=='0':ct+=1
print(ct)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    aa = [S() for _ in range(n-1)]
    a = [[0] * n for _ in range(n)]
    for i in range(n-1):
        s = aa[i]
        t = i + 1
        for j in range(t):
            if s[j] == '1':
                a[t][j] = 1
            else:
                a[j][t] = 1

    r = 0
    for i in range(n):
        ns = set([i])
        ls = set([i])
        while len(ns):
            ts = set()
            for k in ns:
                for j in range(i):
                    if j not in ls and a[k][j]:
                        ts.add(j)

            ls |= ts
            ns = ts

        if len(ls) != i + 1:
            continue

        ns = set([i])
        ls = set([i])
        while len(ns):
            ts = set()
            for k in ns:
                for j in range(i+1,n):
                    if j not in ls and a[k][j]:
                        ts.add(j)

            ls |= ts
            ns = ts

        if len(ls) == n - i:
            r += 1


    return r


print(main())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# m-solutions2019/m_solutions2019_f
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    b = 0
    for x in range(N - 1):
        b ^= int(i2s() + '0' * (N - 2 - x), 2)
    print(b)
    return

main()

Submission status: Wrong Answer

Solution code:
N = int(input())

A = []
ans = 0

for i in range(N-1):
    a = input()
    ans += a.count('0')
    A.append(a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def pbit(aa,L):
    for a in aa:print(format(a,"b").zfill(L))
    print()

def main():
    n=II()
    aa=[[int(c) for c in SI()] for _ in range(n-1)]
    #p2D(aa)
    
    # 人iが勝てる相手をbitで管理する
    win=[0]*n
    for i,row in enumerate(aa,1):
        for j,a in enumerate(row):
            if a:win[i]|=1<<j
            else:win[j]|=1<<i
    #pbit(win,n)

    # dpl[i]...[j,i]の範囲で優勝できるjをbitで
    # dpr[i]...[i,j]の範囲で優勝できるjをbitで
    dpl=[1<<i for i in range(n)]
    dpr=[1<<i for i in range(n)]
    for d in range(1,n):
        for i in range(n):
            j=i+d
            if j<n and dpl[j] & dpr[i+1] & win[i]:dpl[j]|=1<<i
            j=i-d
            if j>=0 and dpl[i-1] & dpr[j] & win[i]:dpr[j]|=1<<i
    #pbit(dpl,n)
    #pbit(dpr,n)
    #print(format(dpl[n-1]&dpr[0],"b").zfill(n))
    print(bin(dpl[n-1]&dpr[0]).count("1"))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=[[int(c) for c in SI()] for _ in range(n-1)]
    #p2D(aa)

    dp=set()
    dp.add((1<<n)-1)
    for _ in range(n-1):
        ndp=set()
        for bit in dp:
            i=j=(bit&-bit).bit_length()-1
            while 1<<i<bit:
                i+=1
                while bit>>i&1==0 and 1<<i<=bit:i+=1
                if 1<<i>bit:break
                if aa[i-1][j]:nbit=bit^1<<j
                else:nbit=bit^1<<i
                ndp.add(nbit)
                j=i
        dp=ndp

    print(len(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def main():
    n=II()
    aa=[[int(c) for c in SI()] for _ in range(n-1)]
    #p2D(aa)

    dp=set()
    dp.add((1<<n)-1)
    for _ in range(n-1):
        ndp=set()
        for bit in dp:
            i=j=(bit&-bit).bit_length()-1
            while 1<<i<bit:
                i+=1
                while bit>>i&1==0 and 1<<i<=bit:i+=1
                if 1<<i>bit:break
                if aa[i-1][j]:nbit=bit^1<<j
                else:nbit=bit^1<<i
                ndp.add(nbit)
                j=i
        dp=ndp

    print(len(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
G = [[] for _ in range(n)]
for i in range(1, n):
  A = map(int, list(input()))
  for j, a in enumerate(A):
    if a:
      G[i].append(j)
    else:
      G[j].append(i)
def dfs(i, left, right):
  l_bool, r_bool = False, False
  if left == i:
    l_bool = True
  if right == i:
    r_bool = True
  for j in G[i]:
    if left <= j < i:
      l_bool |= dfs(j, left, i-1)
    elif i < j <= right:
      r_bool |= dfs(j, i+1, right)
  return l_bool & r_bool

ans = 0
for i in range(n):
  if dfs(i, 0, n-1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
lose = [set() for _ in range(n)]
for i in range(1, n):
  A = map(int, list(input()))
  for j, a in enumerate(A):
    if a:
      lose[j].add(i)
    else:
      lose[i].add(j)
def dfs(i, left, right):
  l_bool, r_bool = False, False
  if left == i:
    l_bool = True
  if right == i:
    r_bool = True
  for j in range(left, i):
    if i in lose[j]:
      l_bool |= dfs(j, left, i-1)
  for j in range(i+1, right+1):
    if i in lose[j]:
      r_bool |= dfs(j, i+1, right)
  return l_bool & r_bool
      
ans = 0
for i in range(n):
  if dfs(i, 0, n-1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
# X = [[1 if i == j else 0 for j in range(N)] for i in range(N)]
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if X[i][j]: Y[i].append(j)

dpl = [[0] * N for _ in range(N)]
dpr = [[0] * N for _ in range(N)]
for i in range(N):
    dpl[i][i] = 1
    dpr[i][i] = 1

for d in range(2, N+1):
    for i in range(N-d+1):
        j = i + d - 1
        for k in range(i+1, j+1):
            if X[i][k] and dpr[i+1][k] and dpl[k][j]:
                dpl[i][j] = 1
                break
        for k in range(i, j):
            if X[j][k] and dpr[i][k] and dpl[k][j-1]:
                dpr[i][j] = 1
                break

print(sum([1 if dpr[0][i] and dpl[i][N-1] else 0 for i in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def l(i, j):
    if i == j: return 1
    for k in range(i+1, j+1):
        if X[i][k] and r(i+1, k) and l(k, j): return 1
    return 0
def r(i, j):
    if i == j: return 1
    for k in range(i, j):
        if X[j][k] and r(i, k) and l(k, j-1): return 1
    return 0

N = int(input())
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if X[i][j]: Y[i].append(j)

print(sum([1 if r(0, i) and l(i, N-1) else 0 for i in range(N)]))

Submission status: Time Limit Exceeded

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

N = int(input())
A = [[0] * N for _ in range(N)]
dpl = [[0] * N for _ in range(N)]
dpr = [[0] * N for _ in range(N)]

for i in range(N) :
    dpl[i][i] = dpr[i][i] = 1

for i in range(1, N) :
    for j, v in enumerate(input()) :
        if v == '1' :
            A[i][j] = 1
        else :
            A[j][i] = 1

for dist in range(1, N) :
    for i in range(N - dist) :
        j = i + dist
        for k in range(i + 1, j + 1) :
            if A[i][k] and dpl[k][j] and dpr[k][i+1] :
                dpl[i][j] = 1
                break
        for k in range(i, j) :
            if A[j][k] and dpl[k][j-1] and dpr[k][i] :
                dpr[j][i] = 1
                break
                
ret = 0
for i in range(N) :
    if dpl[i][N-1] and dpr[i][0] :
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

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

N = int(input())
A = [[0] * N for _ in range(N)]
dpl = [[0] * N for _ in range(N)]
dpr = [[0] * N for _ in range(N)]

for i in range(N) :
    dpl[i][i] = dpr[i][i] = 1

for i in range(1, N) :
    for j, v in enumerate(input()) :
        if v == '1' :
            A[i][j] = 1
        else :
            A[j][i] = 1

for dist in range(1, N) :
    for i in range(N - dist) :
        j = i + dist
        for k in range(i + 1, j + 1) :
            if A[i][k] and dpl[k][j] and dpr[k][i+1] :
                dpl[i][j] = 1
                break
        for k in range(i, j) :
            if A[j][k] and dpl[k][j-1] and dpr[k][i] :
                dpr[j][i] = 1
                break
                
ret = 0
for i in range(N) :
    if dpl[i][N-1] and dpr[i][0] :
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    tab = {'0': '1', '1': '0'}
    N = II()
    A = [['0'] * N for _ in range(N)]
    for i in range(1, N):
        s = SI()
        for j, aa in enumerate(s):
            A[i][j] = aa
            A[j][i] = tab[aa]
    for i in range(N):
        A[i] = int(''.join(A[i])[::-1], 2)
    dpl = [int('1' * N, 2) for _ in range(N)]
    dpr = [int('1' * N, 2) for _ in range(N)]
    for sub in range(1, N):
        for i in range(N - sub):
            j = i + sub
            winr = A[i] & dpl[i + 1] & dpr[j]
            winr = (winr >> (i + 1)) & ((1 << sub) - 1)
            dpr[j] -= (0 if winr else 1) << i
            winl = A[j] & dpl[i] & dpr[j - 1]
            winl = (winl >> i) & ((1 << sub) - 1)
            dpl[i] -= (0 if winl else 1) << j

    ans = bin(dpl[0] & dpr[N - 1]).count('1')
    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from functools import lru_cache

def main():
    N = II()
    A = [[0] * N for _ in range(N)]
    for i in range(1, N):
        s = SI()
        for j, aa in enumerate(s):
            aa = int(aa)
            A[i][j] = aa
            A[j][i] = 1 - aa
    dpl = [[1] * N for _ in range(N)]
    dpr = [[1] * N for _ in range(N)]
    for sub in range(1, N):
        for i in range(N - sub):
            j = i + sub
            winr = 0
            for k in range(i + 1, j + 1):
                if A[i][k] and dpl[i + 1][k] and dpr[k][j]:
                    winr = 1
                    break
            dpr[i][j] = winr
            winl = 0
            for k in range(i, j):
                if A[j][k] and dpl[i][k] and dpr[k][j - 1]:
                    winl = 1
                    break
            dpl[i][j] = winl

    ans = 0
    for i in range(N):
        ans += dpl[0][i] * dpr[i][N - 1]
    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from functools import lru_cache

def main():
    N = II()
    A = [[0] * N for _ in range(N)]
    for i in range(1, N):
        s = SI()
        for j, aa in enumerate(s):
            aa = int(aa)
            A[i][j] = aa
            A[j][i] = 1 - aa
    @lru_cache(maxsize=10**7)
    def win(k, start, end):
        ret = 0 if start != k else 1
        for l in range(start, k):
            if A[k][l] == 1:
                if win(l, start, k):
                    ret = 1
                    break
        if not ret:
            return 0
        ret = 0 if end - 1 != k else 1
        for r in range(k + 1, end):
            if A[k][r] == 1:
                if win(r, k + 1, end):
                    ret = 1
                    break
        return ret
    ans = sum(win(k, 0, N) for k in range(N))

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(1000000)

n = int(input())
people = [i for i in range(n)]
a = [[-1] * n for _ in range(n)]
for i in range(n-1):
    ai = input()
    for j, aij in enumerate(ai):
        a[i+1][j] = int(aij)
        a[j][i+1] = (int(aij) + 1) % 2

memo = {}

# startからendの範囲で優勝の可能性があるやつ
def solve(start, end):
    key = (start, end)
    if key in memo:
        return memo[key]
    if start == end:
        return [start]
    elif start + 1 == end:
        if a[start][end] == 1:
            return [start]
        else:
            return [end]
    winable = set()
    for i in range(start+1, end+1):
        left_winable = solve(start, i-1)
        if (start, i-1) not in memo:
            memo[(start, i-1)] = left_winable
        right_winable = solve(i, end)
        if (i, end) not in memo:
            memo[(i, end)] = right_winable
        for l in left_winable:
            for r in right_winable:
                if a[l][r] == 1:
                    winable.add(l)
                else:
                    winable.add(r)
    return list(winable)


def main():
    winable = solve(0, n-1)
    print(len(winable))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from itertools import accumulate

def main():
    N = II()
    A = [[0] * N for _ in range(N)]
    for i in range(1, N):
        s = SI()
        for j, aa in enumerate(s):
            aa = int(aa)
            A[i][j] = aa
            A[j][i] = 1 - aa
    def win(k, start, end):
        ret = 0 if start != k else 1
        for l in range(start, k):
            if A[k][l] == 1:
                if win(l, start, k):
                    ret = 1
                    break
        if not ret:
            return 0
        ret = 0 if end - 1 != k else 1
        for r in range(k + 1, end):
            if A[k][r] == 1:
                if win(r, k + 1, end):
                    ret = 1
                    break
        return ret
    ans = sum(win(k, 0, N) for k in range(N))

    return ans

print(main())

Submission status: Accepted

Solution code:
import sys

p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def pbit(aa,L):
    for a in aa:print(format(a,"b").zfill(L))
    print()

def main():
    n=II()
    aa=[[int(c) for c in SI()] for _ in range(n-1)]
    #p2D(aa)

    # 人iが勝てる相手をbitで管理する
    win=[0]*n
    for i,row in enumerate(aa,1):
        for j,a in enumerate(row):
            if a:win[i]|=1<<j
            else:win[j]|=1<<i
    #pbit(win,n)

    # dpl[i]...[j,i]の範囲で優勝できるjをbitで
    # dpr[i]...[i,j]の範囲で優勝できるjをbitで
    dpl=[1<<i for i in range(n)]
    dpr=[1<<i for i in range(n)]
    for d in range(1,n):
        for i in range(n-d):
            j=i+d
            if dpl[j] & dpr[i+1] & win[i]:dpl[j]|=1<<i
        for i in range(d,n):
            j=i-d
            if dpl[i-1] & dpr[j] & win[i]:dpr[j]|=1<<i
    #pbit(dpl,n)
    #pbit(dpr,n)
    #print(format(dpl[n-1]&dpr[0],"b").zfill(n))
    print(bin(dpl[n-1]&dpr[0]).count("1"))

main()

Submission status: Accepted

Solution code:
N = int(input())
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1

A = [1<<i for i in range(N)]
B = [1<<i for i in range(N)]
for i in range(N):
    for j in range(i):
        if i and B[i-1] >> j & 1 and X[i][j]: A[i] |= A[j]
    for j in range(i):
        if A[i] >> j+1 & 1 and X[j][i]: B[i] |= B[j]

print(sum([(A[i] & 1) * (B[N-1]>>i & 1) for i in range(N)]))

Submission status: Runtime Error

Solution code:
Q = int(input())
div = 1000003
div_2 = div/2
for _ in range(Q):
  x, d, n = map(int, input())
  q = 1
  for i in range(1, n+1):
    tmp = (x + d*(i-1)) % div
    if tmp > div_2:
      tmp -= div
    q *= tmp
  if q < 0:
    q += div
  print(q)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))

N = int(input())
A = [[]]
for _ in range(N-1):
    A.append(list(map(int,list(input()))))

def match(i,j):
    if i > j:
        return bool(A[i][j])
    else:
        return not bool(A[j][i])

winmem = defaultdict(lambda: None)

def winnerlist(left,right):
    ans = winmem[(left,right)]
    if ans is not None:
        return ans
    elif right - left <= 1:
        return set({left})

    ans = set()
    for i in range(left+1,right):
        left_winners = winnerlist(left,i)
        right_winners = winnerlist(i,right)
        for l in left_winners:
            for r in right_winners:
                if match(l,r):
                    ans.add(l)
                else:
                    ans.add(r)
    winmem[(left,right)] = ans
    return ans

winners = winnerlist(0,N)
print(len(winners))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))

N = int(input())
A = [[]]
for _ in range(N-1):
    A.append(list(map(int,list(input()))))

def match(i,j):
    if i > j:
        return bool(A[i][j])
    else:
        return not bool(A[j][i])

winmem = defaultdict(set)

def winnerlist(left,right):
    ans = winmem[(left,right)]
    if len(ans) > 0:
        return ans
    elif right - left <= 1:
        return set({left})

    ans = set()
    for i in range(left+1,right):
        left_winners = winnerlist(left,i)
        right_winners = winnerlist(i,right)
        for l in list(left_winners):
            for r in list(right_winners):
                if match(l,r):
                    ans.add(l)
                else:
                    ans.add(r)
    winmem[(left,right)] = ans
    return ans

winners = winnerlist(0,N)
print(len(winners))

Submission status: Runtime Error

Solution code:
a = 3
pront "2"