Problem:


Score : 1100 points

Problem Statement

Given is a string S consisting of 0 and 1. Find the number of strings, modulo 998244353, that can result from applying the following operation on S zero or more times:

Remove the two characters at the beginning of S, erase one of them, and reinsert the other somewhere in S. This operation can be applied only when S has two or more characters.

Constraints

1 \leq |S| \leq 300

S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of strings, modulo 998244353, that can result from applying the operation on S zero or more times.

Sample Input 1

0001

Sample Output 1

8

Eight strings, 0001, 001, 010, 00, 01, 10, 0, and 1, can result.

Sample Input 2

110001

Sample Output 2

24

Sample Input 3

11101111011111000000000110000001111100011111000000001111111110000000111111111

Sample Output 3

697354558



Sample input:
0001


Sample output:
8

Submission status: Wrong Answer

Solution code:
import math

X=int(input())
print(360//math.gcd(360,X))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    s=input()
    l1=sum(map(int, s))
    l=len(s)
    l0=l-l1
    dp=[[[0]*(l1+1) for _ in range(l0+1)] for _ in range(l+1)]
    dp[0][0][0]=1
    dp[1][0][0]=1
    def extgcd1(a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b: t=a//b; a-=t*b; a,b=b,a; u,v=v,u-t*v
        if a!=1: return -1#互いに素じゃない
        return u%b0
    
    maxn=l
    fact=[1]*(maxn+1)#NはnCrの最大のn
    ifact=[1]*(maxn+1)
    x=1
    for i in range(2,maxn+1):
        x=(x*i)%mod
        fact[i]=x
        ifact[i]=extgcd1(x,mod)
    def comb(n,r): 
        if n<0 or r>n:
            return 0
        return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod

    for k in range(2,l+1):
        for i in range(min(l0+1,k+1)):
            for j in range(min(l1+1,k-i+1)):
                dp[k][i][j]=dp[k-1][i][j]
                if s[k-1]=="0" and i>0 and j+1<=l1:
                    dp[k][i][j]|=dp[k-1][i-1][j+1]
                elif s[k-1]=="1" and j>0 and i+1<=l0:
                    dp[k][i][j]|=dp[k-1][i+1][j-1]
                if s[k-2]=="0" and i>0:
                    dp[k][i][j]|=dp[k-2][i-1][j]
                if s[k-2]=="1" and j>0:
                    dp[k][i][j]|=dp[k-2][i][j-1]
                #print(s[k-1],i,j)
    ans=0
    
    # dp2=[[[0]*(l1+1) for _ in range(l0+1)] for _ in range(l+1)]
    # dp2[0][0][0]=1
    pl1=0
    pl0=0
    for k in range(l+1):
        if k==l:
            ans+=1
            ans%=mod
            break
        if s[-k-1]=="0":
            pl1+=1
        else:pl0+=1
        for i in range(l0+1):
            for j in range(l1+1):
                if not dp[l-k][i][j]: continue
                x=0
                if i+j==0:
                    x=1
                elif i==0:
                    x=comb(pl1+j-1,j)
                elif j==0:
                    x=comb(pl0+i-1,i)
                else:
                    x=comb(pl0+i-1,i)*comb(pl1+j-1,j)

                #print(k,pl0,pl1,i,j,x)
                ans+=x
                ans%=mod
        #print(ans)
                
    ans=(ans-1)%mod
    print(ans)
    #print(dp[2])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
N = 2*10**3
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inverse = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

import time
S=input()
N=len(S)
#print(N)
start=time.time()
if N==1:
    exit(print(1))

dp=[[[-10**5 for i in range(N+2)] for j in range(N+2)] for k in range(N+1)]
dpf=[[[-10**5 for i in range(N+2)] for j in range(N+2)] for k in range(N+1)]

dpf[0][0][0]=1
if S[0]=="0":
    dpf[1][1][0]=0
if S[1]=="0":
    dp[1][1][0]=0
if S[0]=="1":
    dpf[1][0][1]=0
if S[1]=="1":
    dp[1][0][1]=0
dpf[1][0][0]=2
Zero=1-int(S[0])+1-int(S[1])
One=int(S[0])+int(S[1])
for i in range(2,N):
    Zero+=1-int(S[i])
    One+=int(S[i])
    for j in range(Zero+1):
        for k in range(One+1):
            a,b=1-int(S[i]),int(S[i])
            dp[i][j][k]=max(dp[i-1][j-a][k-b]-2,dpf[i-1][j-a][k-b]-1)
            a,b=1-int(S[i-1]),int(S[i-1])
            if dp[i-2][j-a][k-b]>=0:
                dpf[i][j][k]=2*(dp[i-2][j-a][k-b]//2)
            if dpf[i-2][j-a][k-b]>=0:
                dpf[i][j][k]=max(2*(dpf[i-2][j-a][k-b]//2),dpf[i][j][k])
            if dp[i-1][j][k]>=0:
                dpf[i][j][k]=max(dp[i-1][j][k]+1-dp[i-1][j][k]%2,dpf[i][j][k])
            dpf[i][j][k]=max(dpf[i][j][k],dpf[i-1][j][k]+1)
    dpf[i][0][0]=i+1

data=[[[(dp[i][j][k]>=0 or dpf[i][j][k]>=0)&((j,k)!=(0,0)) for k in range(N+1)] for j in range(N+1)] for i in range(N)]
med=time.time()
#print(med-start)

S=[S[-i-1] for i in range(N)]
Zero=0
One=0
ans=1
check=set([])
one,zero=S.count("1"),S.count("0")
for i in range(N):
    Zero+=(S[i]=="1")
    One+=(S[i]=="0")
    for j in range(zero+1):
        for k in range(one+1):
            if data[N-1-i][j][k]:
                check.add((j,k))
    ncheck=set([])
    for j,k in check:
        A,B=1,1
        if j!=0:
            A=cmb(Zero+j-1,j,mod)
        if k!=0:
            B=cmb(One+k-1,k,mod)
        ans+=A*B
        ans%=mod
        a,b=1-int(S[i]),int(S[i])
        if j>=a and k>=b:
            ncheck.add((j-a,k-b))
    check=ncheck
    zero-=1-int(S[i])
    one-=int(S[i])

print(ans)

def check():
    res=0
    for i in range(N):
        for j in range(N+1):
            for k in range(N+1) :
                if data[i][j][k]:
                    print(i,j,k)
                    res+=1
    return res
#print(time.time()-start)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(s):
    n = len(s)
    size = n // 2
    MOD = 998244353
    dp_can = np.zeros((n + 1, size + 1, size + 1), dtype=np.int8)
    dp_cnt = np.zeros((n + 1, size + 1, size + 1), dtype=np.int64)

    dp_cnt[n, 0] = 1
    for j in range(size):
        dp_cnt[n, j + 1] = np.cumsum(dp_cnt[n, j]) % MOD

    for i in range(n - 1, -1, -1):
        if s[i] == '0':
            dp_cnt[i] = np.cumsum(dp_cnt[i + 1], axis=1) % MOD
        else:
            dp_cnt[i] = np.cumsum(dp_cnt[i + 1], axis=0) % MOD

    dp_can[0, 0, 0] = 1
    for i in range(n):
        dp_can[i + 1] |= dp_can[i]
        if s[i] == '0':
            dp_can[i + 1, 1:, :-1] |= dp_can[i, :-1, 1:]
        else:
            dp_can[i + 1, :-1, 1:] |= dp_can[i, 1:, :-1]
        if i < n - 1:
            if s[i] == '0' or s[i + 1] == '0':
                dp_can[i + 2, 1:, :] |= dp_can[i, :-1, :]
            if s[i] == '1' or s[i + 1] == '1':
                dp_can[i + 2, :, 1:] |= dp_can[i, :, :-1]
    dp_can[1:, 0, 0] = 0

    ans = 0

    for i in range(n, -1, -1):
        for j in range(size + 1):
            for k in range(size + 1):
                if dp_can[i, j, k] == 0:
                    continue

                ans = (ans + dp_cnt[i, j, k]) % MOD

                a, b = j, k
                for h in range(i - 1, -1, -1):
                    if s[h] == '0':
                        a -= 1
                    else:
                        b -= 1
                    if a < 0 or b < 0:
                        break
                    dp_can[h, a, b] = 0

    return ans


s = input()
ans = solve(s)
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
N = 2*10**3
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inverse = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

import time
S=input()
N=len(S)
#print(N)
start=time.time()
if N==1:
    exit(print(1))

dp=[[[-10**15 for i in range(N+2)] for j in range(N+2)] for k in range(N+1)]
dpf=[[[-10**15 for i in range(N+2)] for j in range(N+2)] for k in range(N+1)]

dpf[0][0][0]=1
if S[0]=="0":
    dp[1][1][0]=0
if S[1]=="0":
    dp[1][1][0]=0
if S[0]=="1":
    dp[1][0][1]=0
if S[1]=="1":
    dp[1][0][1]=0
dpf[1][0][0]=2
Zero=1-int(S[0])+1-int(S[1])
One=int(S[0])+int(S[1])
for i in range(2,N):
    Zero+=1-int(S[i])
    One+=int(S[i])
    for j in range(Zero+1):
        for k in range(One+1):
            a,b=1-int(S[i]),int(S[i])
            dp[i][j][k]=max(dp[i-1][j-a][k-b]-2,dpf[i-1][j-a][k-b]-1)
            a,b=1-int(S[i-1]),int(S[i-1])
            dpf[i][j][k]=max(dpf[i-1][j][k]+1,dp[i-1][j][k]+1-dp[i-1][j][k]%2)
            dp[i][j][k]=max(dp[i][j][k],2*(dpf[i-2][j-a][k-b]//2),2*(dp[i-2][j-a][k-b]//2))
            if dp[i][j][k]<0:
              dp[i][j][k]=-10**5
            if dpf[i][j][k]<0:
              dpf[i][j][k]=-10**5
    dpf[i][0][0]=i+1

med=time.time()
#print(med-start)

S=[S[-i-1] for i in range(N)]
Zero=0
One=0
ans=1
check=set([])
one,zero=S.count("1"),S.count("0")
for i in range(N):
    Zero+=(S[i]=="1")
    One+=(S[i]=="0")
    for j in range(zero+1):
        for k in range(one+1):
            if (dp[N-1-i][j][k]>=0 or dpf[N-1-i][j][k]>=0) and (j,k)!=(0,0):
                check.add((j,k))
    ncheck=set([])
    for j,k in check:
        A,B=1,1
        if j!=0:
            A=cmb(Zero+j-1,j,mod)
        if k!=0:
            B=cmb(One+k-1,k,mod)
        ans+=A*B
        ans%=mod
        a,b=1-int(S[i]),int(S[i])
        if j>=a and k>=b:
            ncheck.add((j-a,k-b))
    check=ncheck
    zero-=1-int(S[i])
    one-=int(S[i])

print(ans)

def check():
    res=0
    for i in range(N):
        for j in range(N+1):
            for k in range(N+1) :
                if data[i][j][k]:
                    print(i,j,k)
                    res+=1
    return res
#print(time.time()-start)

Submission status: Accepted

Solution code:
import numpy as np
import numba as nb


@nb.njit('(i1[:],)', cache=True)
def solve(s):
    n = len(s)
    size = n // 2
    MOD = 998244353
    dp_can = np.zeros((n + 1, size + 1, size + 1), dtype=np.int8)
    dp_cnt = np.zeros((n + 1, size + 1, size + 1), dtype=np.int64)

    dp_cnt[n, 0] = 1
    for j in range(size):
        dp_cnt[n, j + 1] = np.cumsum(dp_cnt[n, j]) % MOD

    for i in range(n - 1, -1, -1):
        if s[i] == 0:
            for j in range(size + 1):
                dp_cnt[i, j] = np.cumsum(dp_cnt[i + 1, j]) % MOD
        else:
            for k in range(size + 1):
                dp_cnt[i, :, k] = np.cumsum(dp_cnt[i + 1, :, k]) % MOD

    dp_can[0, 0, 0] = 1
    for i in range(n):
        for j in range(size):
            for k in range(size):
                if dp_can[i, j, k] == 0:
                    continue
                dp_can[i + 1, j, k] = 1
                if j > 0 and s[i] == 1:
                    dp_can[i + 1, j - 1, k + 1] = 1
                if k > 0 and s[i] == 0:
                    dp_can[i + 1, j + 1, k - 1] = 1
                if i < n - 1:
                    if s[i] == 0 or s[i + 1] == 0:
                        dp_can[i + 2, j + 1, k] = 1
                    if s[i] == 1 or s[i + 1] == 1:
                        dp_can[i + 2, j, k + 1] = 1
    dp_can[1:, 0, 0] = 0

    ans = 0

    for i in range(n, -1, -1):
        for j in range(size + 1):
            for k in range(size + 1):
                if dp_can[i, j, k] == 0:
                    continue

                ans = (ans + dp_cnt[i, j, k]) % MOD

                a, b = j, k
                for h in range(i - 1, -1, -1):
                    if s[h] == 0:
                        a -= 1
                    else:
                        b -= 1
                    if a < 0 or b < 0:
                        break
                    dp_can[h, a, b] = 0

    return ans


s = np.array([int(c) for c in input()], dtype=np.int8)
print(solve(s))

Submission status: Accepted

Solution code:
import numpy as np
import numba as nb


@nb.njit('(i1[:],)', cache=True)
def solve(s):
    n = len(s)
    size = n // 2
    MOD = 998244353
    dp_can = np.zeros((n + 1, size + 1, size + 1), dtype=np.int8)
    dp_cnt = np.zeros((n + 1, size + 1, size + 1), dtype=np.int64)

    dp_cnt[n, 0] = 1
    for j in range(size):
        dp_cnt[n, j + 1] = np.cumsum(dp_cnt[n, j]) % MOD

    for i in range(n - 1, -1, -1):
        if s[i] == 0:
            for j in range(size + 1):
                dp_cnt[i, j] = np.cumsum(dp_cnt[i + 1, j]) % MOD
        else:
            for k in range(size + 1):
                dp_cnt[i, :, k] = np.cumsum(dp_cnt[i + 1, :, k]) % MOD

    dp_can[0, 0, 0] = 1
    for i in range(n):
        dp_can[i + 1] |= dp_can[i]
        if s[i] == 0:
            dp_can[i + 1, 1:, :-1] |= dp_can[i, :-1, 1:]
        else:
            dp_can[i + 1, :-1, 1:] |= dp_can[i, 1:, :-1]
        if i < n - 1:
            if s[i] == 0 or s[i + 1] == 0:
                dp_can[i + 2, 1:, :] |= dp_can[i, :-1, :]
            if s[i] == 1 or s[i + 1] == 1:
                dp_can[i + 2, :, 1:] |= dp_can[i, :, :-1]
    dp_can[1:, 0, 0] = 0

    ans = 0

    for i in range(n, -1, -1):
        for j in range(size + 1):
            for k in range(size + 1):
                if dp_can[i, j, k] == 0:
                    continue

                ans = (ans + dp_cnt[i, j, k]) % MOD

                a, b = j, k
                for h in range(i - 1, -1, -1):
                    if s[h] == 0:
                        a -= 1
                    else:
                        b -= 1
                    if a < 0 or b < 0:
                        break
                    dp_can[h, a, b] = 0

    return ans


s = np.array([int(c) for c in input()], dtype=np.int8)
print(solve(s))

Submission status: Runtime Error

Solution code:
import math
X = int(input())
lcm = 360 * X // math.gcd(360, X)
print(lcm // X)

Submission status: Runtime Error

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
N = 2*10**3
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inverse = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0


S=input()
N=len(S)

dp=[[[-10**5 for i in range(N+2)] for j in range(N+2)] for k in range(N+1)]
dpf=[[[-10**5 for i in range(N+2)] for j in range(N+2)] for k in range(N+1)]

dpf[0][0][0]=1
if S[0]=="0":
    dpf[1][1][0]=0
if S[1]=="0":
    dp[1][1][0]=0
if S[0]=="1":
    dpf[1][0][1]=0
if S[1]=="1":
    dp[1][0][1]=0
dpf[1][0][0]=2
for i in range(2,N):
    for j in range(N+1):
        for k in range(N+1):
            a,b=1-int(S[i]),int(S[i])
            dp[i][j][k]=max(dp[i-1][j-a][k-b]-2,dpf[i-1][j-a][k-b]-1)
            a,b=1-int(S[i-1]),int(S[i-1])
            if dp[i-2][j-a][k-b]>=0:
                dpf[i][j][k]=2*(dp[i-2][j-a][k-b]//2)
            if dpf[i-2][j-a][k-b]>=0:
                dpf[i][j][k]=max(2*(dpf[i-2][j-a][k-b]//2),dpf[i][j][k])
            if dp[i-1][j][k]>=0:
                dpf[i][j][k]=max(dp[i-1][j][k]+1-dp[i-1][j][k]%2,dpf[i][j][k])
            dpf[i][j][k]=max(dpf[i][j][k],dpf[i-1][j][k]+1)
    dpf[i][0][0]=i+1

data=[[[(dp[i][j][k]>=0 or dpf[i][j][k]>=0)&((j,k)!=(0,0)) for k in range(N+1)] for j in range(N+1)] for i in range(N)]

S=[S[-i-1] for i in range(N)]
Zero=0
One=0
ans=1
check=set([])
for i in range(N):
    Zero+=(S[i]=="1")
    One+=(S[i]=="0")
    for j in range(N+1):
        for k in range(N+1):
            if data[N-1-i][j][k]:
                check.add((j,k))
    ncheck=set([])
    for j,k in check:
        A,B=1,1
        if j!=0:
            A=cmb(Zero+j-1,j,mod)
        if k!=0:
            B=cmb(One+k-1,k,mod)
        ans+=A*B
        ans%=mod
        a,b=1-int(S[i]),int(S[i])
        if j>=a and k>=b:
            ncheck.add((j-a,k-b))
    check=ncheck

print(ans)

def check():
    res=0
    for i in range(N):
        for j in range(N+1):
            for k in range(N+1) :
                if data[i][j][k]:
                    print(i,j,k)
                    res+=1
    return res