Problem:


Score : 800 points

Problem Statement

Snuke has a string x of length N.
Initially, every character in x is 0.

Snuke can do the following two operations any number of times in any order:

Choose A consecutive characters in x and replace each of them with 0.

Choose B consecutive characters in x and replace each of them with 1.

Find the number of different strings that x can be after Snuke finishes doing operations.
This count can be enormous, so compute it modulo (10^9+7).

Constraints

1 \leq N \leq 5000

1 \leq A,B \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B

Output

Print the number of different strings that x can be after Snuke finishes doing operations, modulo (10^9+7).

Sample Input 1

4 2 3

Sample Output 1

11

For example, x can be 0011 or 1111 in the end, but cannot be 0110.

Sample Input 2

10 7 2

Sample Output 2

533

Sample Input 3

1000 100 10

Sample Output 3

828178524



Sample input:
4 2 3


Sample output:
11

Submission status: Wrong Answer

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


#11-


n,aa,bb = list(map(int, input().split()))

a = max(aa,bb)
b = min(aa,bb)
p = 1000000007

xs0 = [0]*(n+1)
os0 = [0]*(n+1)

os0[0] = 1

for i in range(b,a-1):
    for j in range(b,i+1):
        xs0[i] += os0[i-j]
        xs0[i] %= p
    for j in range(1,i+1):
        os0[i] += xs0[i-j]
        os0[i] %= p

#print(xs0[:50])
#print(os0[:50])

os = [0]*a

for i in range(b,a-2): #number-x
    for j in range(2,a-i): # adding o
        os[i+j] += xs0[i] * (j-1)

x = [0]*(n+1)
o = [0]*(n+1)

for i in range(b+1,a-1): # adding distination
    for j in range(b,i): # length of xs
        o[i] += xs0[j]
        o[i] %= p

x[0] = 1
o[0] = 1

for i in range(1,n+1):
    for j in range(1,min(b,i+1)):
        x[i] += o[i-j]
    for j in range(1,min(a,i+1)):
        o[i] += x[i-j]
    for j in range(b+2,min(a,i+1)):
        o[i] += x[i-j]*os[j]
    x[i] %= p
    o[i] %= p

for i in range(b+1,a-1):
    for j in range(b,i):
        o[n] += xs0[j] * x[n-i]
        o[i]%=p

ans = o[n] + x[n]
ans %= p

#print(ans)

beki2 = [1]*5001

for i in range(5000):
    beki2[i+1] = beki2[i]*2
    beki2[i+1] %= p

ans = beki2[n] - ans
ans += p
ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
def combination_mod(n, r, mod):
    # フェルマーの小定理
    # nCr=n!(r!)^p-2((n-r)!)^p-2

    n_ = 1
    for i in range(1, n + 1):
        n_ = (n_ * i) % mod
    r_ = 1
    for i in range(1, r + 1):
        r_ = (r_ * i) % mod
    nr_ = 1
    for i in range(1, n - r + 1):
        nr_ = (nr_ * i) % mod

    power_r = pow(r_, mod - 2, mod)
    power_nr = pow(nr_, mod - 2, mod)

    return (n_ * power_r * power_nr) % mod


def main():
    N,A,B=map(int,input().split())

    mod=pow(10,9)+7

    PatternA=0
    PatternB=0

    #PatternA
    for a in range(1,N-A+2):
        PatternA+=combination_mod(N-(A-1),a,mod)
    #PatternB
    for b in range(1,N-B+2):
        PatternB+=combination_mod(N-(B-1),b,mod)

    res=PatternA+PatternB

    print(res+1)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def combination_mod(n, r, mod):
    # フェルマーの小定理
    # nCr=n!(r!)^p-2((n-r)!)^p-2

    n_ = 1
    for i in range(1, n + 1):
        n_ = (n_ * i) % mod
    r_ = 1
    for i in range(1, r + 1):
        r_ = (r_ * i) % mod
    nr_ = 1
    for i in range(1, n - r + 1):
        nr_ = (nr_ * i) % mod

    power_r = pow(r_, mod - 2, mod)
    power_nr = pow(nr_, mod - 2, mod)

    return (n_ * power_r * power_nr) % mod


def main():
    N,A,B=map(int,input().split())

    mod=pow(10,9)+7

    PatternA=0
    PatternB=0

    #PatternA
    for a in range(N-(A-1)):
        PatternA+=combination_mod(N-(A-1),a,mod)
    #PatternB
    for b in range(N-(B-1)):
        PatternB+=combination_mod(N-(B-1),b,mod)

    res=PatternA+PatternB

    print(res+1)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
#from math import *
from heapq import *
from typing import List
from itertools import *
#from operator import *
from functools import *
import sys
'''
@lru_cache(None)
def fact(x):
    if x<2:
        return 1
    return fact(x-1)*x

@lru_cache(None)
def per(i,j):
    return fact(i)//fact(i-j)

@lru_cache(None)
def com(i,j):
    return per(i,j)//fact(j)

def linc(f,t,l,r):
    while l<r:
        mid=(l+r)//2
        if t>f(mid):
            l=mid+1
        else:
            r=mid
    return l

def rinc(f,t,l,r):
    while l<r:
        mid=(l+r+1)//2
        if t<f(mid):
            r=mid-1
        else:
            l=mid
    return l

def ldec(f,t,l,r):
    while l<r:
        mid=(l+r)//2
        if t<f(mid):
            l=mid+1
        else:
            r=mid
    return l

def rdec(f,t,l,r):
    while l<r:
        mid=(l+r+1)//2
        if t>f(mid):
            r=mid-1
        else:
            l=mid
    return l

def isprime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

def power2(n):
    while not n&1:
        n>>=1
    return n==1
'''
sys.setrecursionlimit(10000)
mod=10**9+7
n,a,b=map(int,input().split())
if a>b:
    a,b=b,a
@lru_cache(None)
def dp(i,bit,carry):
    if i==n:
        return 1
    if i>n:
        return 0
    tmp=0
    if bit==0:
        for j in range(1,max(a,b-carry)):
            tmp=(tmp+dp(i+j,1,0 if j<a else carry+j))%mod
    else:
        for j in range(1,b-carry):
            tmp=(tmp+dp(i+j,0,carry+j))%mod
    return tmp
ans=pow(2,n,mod)
if b==1:
    print(ans)
else:
    ans=(ans-dp(0,0,0)-dp(0,1,0))%mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
n, a, b = map(int, input().split())

if a > b:
    a, b = b, a

dp_1s = [0] * b
for l in range(a + 2, b):
    dp = [[0, 0] for _ in range(l + 1)] # at i, 0/1 precedes
    dp[1][1] = 1
    for i in range(1, l):
        dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % MOD
        dp[i + 1][1] = (dp[i + 1][1] + dp[i][0] + dp[i][1]) % MOD
        if i + a < l:
            dp[i + a][0] = (dp[i + a][0] + dp[i][1]) % MOD
    dp_1s[l] = dp[l][1] - 1

dp_0s_edge = [0] * b
for l in range(a + 1, b):
    dp = [[0, 0] for _ in range(l + 1)]
    dp[a][0] = 1
    for i in range(1, l):
        dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % MOD
        dp[i + 1][1] = (dp[i + 1][1] + dp[i][0] + dp[i][1]) % MOD
        if i + a < l:
            dp[i + a][0] = (dp[i + a][0] + dp[i][1]) % MOD
    dp_0s_edge[l] = dp[l][1] 

# starting at i, 0s/1s precede, i.e., 1s/0s follow
# when 0s precede, len of preceding 0s is lt a
dp = [[0, 0] for _ in range(n + 1)]

dp[0] = [1, 1]
# starting with 0s whose len is gt or eq to a
for l in range(a + 1, b):
    dp[l][1] = dp_0s_edge[l]

for i in range(n):
    for j in range(i + 1, min(n + 1, i + b)):
        dp[j][1] = (dp[j][1] + dp[i][0]) % MOD
    for j in range(i + 1, min(n + 1, i + a)):
        dp[j][0] = (dp[j][0] + dp[i][1]) % MOD
    for l in range(a + 2, b):
        if i + l <= n:
            dp[i + l][1] = (dp[i + l][1] + dp[i][0] * dp_1s[l]) % MOD

# ending with 0s whose len is gt or eq to a
for l in range(a + 1, b):
    dp[n][0] = (dp[n][0] + dp[n - l][0] * dp_0s_edge[l]) % MOD

print((pow(2, n, MOD) - sum(dp[n])) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n,aa,bb = list(map(int, input().split()))

a = max(aa,bb)
b = min(aa,bb)
p = 1000000007

def calc(a,b,p):

    xs0 = [0]*(n+1)
    os0 = [0]*(n+1)
    
    os0[0] = 1
    
    for i in range(b,a-1):
        for j in range(b,i+1):
            xs0[i] += os0[i-j]
            xs0[i] %= p
        for j in range(1,i+1):
            os0[i] += xs0[i-j]
            os0[i] %= p
    
    
    #print(xs0[:50])
    #print(os0[:50])
    
    os = [0]*a
    
    for i in range(b,a-2): #number-x
        for j in range(2,a-i): # adding o
            os[i+j] += xs0[i] * (j-1)
    
    x = [0]*(n+1)
    o = [0]*(n+1)
    
    for i in range(b+1,a): # adding distination
        for j in range(b,i): # length of xs
            o[i] += xs0[j]
            o[i] %= p
    
    x[0] = 1
    o[0] = 1
    
    for i in range(1,n+1):
        for j in range(1,min(b,i+1)):
            x[i] += o[i-j]
        for j in range(1,min(a,i+1)):
            o[i] += x[i-j]
        for j in range(b+2,min(a,i+1)):
            o[i] += x[i-j]*os[j]
        x[i] %= p
        o[i] %= p
    
    for i in range(b+1,a):
        for j in range(b,i):
            o[n] += xs0[j] * x[n-i]
            o[i]%=p
    
    ans = o[n] + x[n]
    ans %= p
    
    #print(ans)
    
    beki2 = [1]*5001
    
    for i in range(5000):
        beki2[i+1] = beki2[i]*2
        beki2[i+1] %= p
    
    ans = beki2[n] - ans
    ans += p
    ans %= p
    return ans

print(calc(a,b,p))

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
mod=10**9+7

A,B=min(A,B),max(A,B)

data=[0]*B
data[0]=1
for i in range(1,B):
    data[i]=(data[i-1]+sum(data[i-1-k] for k in range(A,i)))%mod

#print(data)

dp=[0]*(N+1)
dp[0]=1
imos=[0]*(N+1)
imos[0]=1

for i in range(1,N+1):
    if i!=N:
        for j in range(1,min(i,B)):
            #dp[i]+=sum(dp[i-j-k]*data[j-1] for k in range(1,min(A,i-j+1)))
            R=i-j-1
            L=i-j-min(A,i-j+1)
            if R>L:
                if L>-1:
                    dp[i]+=(imos[R]-imos[L])*data[j-1]
                else:
                    dp[i]+=imos[R]*data[j-1]
                dp[i]%=mod
        if B>i:
            dp[i]+=data[i]
            dp[i]%=mod
    else:
        for j in range(B):
            #dp[i]+=sum(dp[i-j-k]*data[j] for k in range(1,min(A,i-j+1)))
            R=i-j-1
            L=i-j-min(A,i-j+1)
            if R>L:
                if L>-1:
                    dp[i]+=(imos[R]-imos[L])*data[j]
                else:
                    dp[i]+=imos[R]*data[j]
                dp[i]%=mod
        #print(dp[i])
        #dp[i]+=sum(dp[i-k] for k in range(1,A))
    imos[i]=dp[i]
    imos[i]+=imos[i-1]
    imos[i]%=mod


#print(dp)
print((pow(2,N,mod)-dp[N])%mod)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2

すべて0にする、すべて1にするは自明に可能
なので A >= B としてよい(A<Bの時は01を入れ替えて考えればよい)

最後に置いた場所の周囲がどんな状況か考える

0*Aがある場合、その周囲はすべての場合構成可能
ない場合は…？
1*Bがある場合を考える。長さB以上の1列は後からおけるからおｋだが…
長さB以上の1をすべて0に変えたときに、長さA以上の0があればおｋ

どう数え上げる？
ダメな場合を引くのがよさそう？
→dp[i][last][num] = i番目まで見て、lastを現在num個連続しておいている場合の通り数
ただし、dp[?][1][B-1]はdp[?][0][B]に伝播する
これまずいか

ブロックで考えるやり方はどうなんだろう
つまり、連鎖を断ち切れるのは長さB以下の1列だけ

0 or B以上連続する1の列のみで構成されたブロックX(Yに隣接する端は0である必要あり)
B未満の1列であるブロックYを交互に置いていく

dp[i][XorY] = i番目の文字を次に置けるとき、最後に置いたブロックがXorYの時の通り数
初期値は
dp[0][X] = 1
dp[0][Y] = 1 ←これ、かなり注意する必要がある左端が1でもいいから
同様に、Nに移行する時にXを置くときも右端を1にできるのに注意

B以上連続する1を0に変えるとすべて0になる文字列の数をまず求める
上と同様にブロックdp?
0のブロックは,1以上のどんな長さでも置ける
1のブロックは,B以上の長さ置ける
dp[0][Z] = 1
dp[0][O] = 1

"""

N,A,B = map(int,input().split())

fdp = [[0,0] for i in range(N+1)]
fdp[0] = [1,1]
mod = 10**9+7

if A < B:
    tmp = B
    B = A
    A = tmp

for i in range(N):

    for j in range(i+1,N+1):
        fdp[j][0] += fdp[i][1]
        fdp[j][0] %= mod

    for j in range(i+B,N+1):
        fdp[j][1] += fdp[i][0]
        fdp[j][1] %= mod

#print (fdp)

dp = [[0,0] for i in range(N+1)]
dp[0] = [1,1]

for i in range(N):

    for j in range(i+1,min(N+1,i+B)):
        dp[j][1] += dp[i][0]
        dp[j][1] %= mod

    #ここかなり注意
    for j in range(i+1,min(N+1,i+A)):

        l = j-i

        if i == 0 or j == N:
            if l == 1:
                dp[j][0] += dp[i][1]
                dp[j][0] %= mod
            else:
                dp[j][0] += dp[i][1] * sum(fdp[l-1])
                dp[j][0] %= mod

        else:
            if l <= 2:
                dp[j][0] += dp[i][1]
                dp[j][0] %= mod
            else:
                dp[j][0] += dp[i][1] * sum(fdp[l-2])
                dp[j][0] %= mod

#print (dp)          
print ((pow(2,N,mod)-sum(dp[N])) % mod)

Submission status: Accepted

Solution code:
def solve(n, a, b):
    MOD = 10 ** 9 + 7
    if a > b:
        a, b = b, a
    if a == 1:
        return pow(2, n, MOD)

    # 長さ i の区間であり、右端が '1' であり、
    # はじめ '1' で塗りつぶされていたのを、
    # 長さ a 以上の '0' で0回以上上書きすることで実現できる並びの個数
    dp1 = [0] * (b + 1)
    dp1_acc = [0] * (b + 1)
    dp1[0] = 1
    dp1_acc[0] = 1

    for i in range(1, b + 1):
        tmp = dp1[i - 1]  # 末尾に1を付ける
        if i - a - 1 >= 0:
            tmp = (tmp + dp1_acc[i - a - 1]) % MOD  # 末尾に 00..01 を付ける
        dp1[i] = tmp
        dp1_acc[i] = (dp1_acc[i - 1] + tmp) % MOD
    # 派生情報
    # dp1[i-1]: 長さ i の区間であり、「両端」が'1'であるものの個数
    # dp1[i] - dp1[i-1]: 長さ i の区間であり、左端が'0'、右端が'1'（またはその逆）のものの個数

    # dp2x[i]
    # 長さ i の区間であり、末尾が x であり、
    # 長さa以上の'0'も、長さb以上の'1'も含まない01の並びの個数
    # ただし'1'は、dp1で求めたように、その内部をa個以上の'0'で置きかえたものも含む
    dp20 = [0] * (n + 1)
    dp21 = [0] * (n + 1)
    dp21_acc = [0] * (n + 1)
    dp20[0] = dp21[0] = dp21_acc[0] = 1
    for i in range(1, n + 1):
        t0 = dp21_acc[i - 1]
        if i >= a:
            t0 -= dp21_acc[i - a]
        dp20[i] = t0 % MOD

        t1 = 0
        for j in range(1, min(i + 1, b)):
            t1 += dp20[i - j] * dp1[j - 1]
        # 左端が '111...' でb個以上取れないもので、さらに'0'で置きかえられた結果、最左端が'0'のもの
        if i < b:
            t1 += dp1[i] - dp1[i - 1]
        t1 %= MOD
        dp21[i] = t1
        dp21_acc[i] = (dp21_acc[i - 1] + t1) % MOD

    disable = dp20[n] + dp21[n]

    # 最後が'111..'でb個以上取れないもので、
    # さらに'0'で置きかえられた結果、右端が'0'のものが数えられていない
    for i in range(1, b):
        disable += dp20[n - i] * (dp1[i] - dp1[i - 1])

    return (pow(2, n, MOD) - disable) % MOD


n, a, b = map(int, input().split())
print(solve(n, a, b))

Submission status: Accepted

Solution code:


n,aa,bb = list(map(int, input().split()))

a = max(aa,bb)
b = min(aa,bb)
p = 1000000007

xs0 = [0]*(n+1)
os0 = [0]*(n+1)

os0[0] = 1

for i in range(b,a-1):
    for j in range(b,i+1):
        xs0[i] += os0[i-j]
        xs0[i] %= p
    for j in range(1,i+1):
        os0[i] += xs0[i-j]
        os0[i] %= p


#print(xs0[:50])
#print(os0[:50])

os = [0]*a

for i in range(b,a-2): #number-x
    for j in range(2,a-i): # adding o
        os[i+j] += xs0[i] * (j-1)

x = [0]*(n+1)
o = [0]*(n+1)

for i in range(b+1,a): # adding distination
    for j in range(b,i): # length of xs
        o[i] += xs0[j]
        o[i] %= p

x[0] = 1
o[0] = 1

for i in range(1,n+1):
    for j in range(1,min(b,i+1)):
        x[i] += o[i-j]
    for j in range(1,min(a,i+1)):
        o[i] += x[i-j]
    for j in range(b+2,min(a,i+1)):
        o[i] += x[i-j]*os[j]
    x[i] %= p
    o[i] %= p

for i in range(b+1,a):
    for j in range(b,i):
        o[n] += xs0[j] * x[n-i]
        o[i]%=p

ans = o[n] + x[n]
ans %= p

#print(ans)

beki2 = [1]*5001

for i in range(5000):
    beki2[i+1] = beki2[i]*2
    beki2[i+1] %= p

ans = beki2[n] - ans
ans += p
ans %= p

print(ans)

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


#11-


n,aa,bb = list(map(int, input().split()))

a = max(aa,bb)
b = min(aa,bb)
p = 1000000007

xs0 = [0]*(n+1)
os0 = [0]*(n+1)

os0[0] = 1

for i in range(b,a-1):
    for j in range(b,i+1):
        xs0[i] += os0[i-j]
        xs0[i] %= p
    for j in range(1,i+1):
        os0[i] += xs0[i-j]
        os0[i] %= p


#print(xs0[:50])
#print(os0[:50])

os = [0]*a

for i in range(b,a-2): #number-x
    for j in range(2,a-i): # adding o
        os[i+j] += xs0[i] * (j-1)

x = [0]*(n+1)
o = [0]*(n+1)

for i in range(b+1,a): # adding distination
    for j in range(b,i): # length of xs
        o[i] += xs0[j]
        o[i] %= p

x[0] = 1
o[0] = 1

for i in range(1,n+1):
    for j in range(1,min(b,i+1)):
        x[i] += o[i-j]
    for j in range(1,min(a,i+1)):
        o[i] += x[i-j]
    for j in range(b+2,min(a,i+1)):
        o[i] += x[i-j]*os[j]
    x[i] %= p
    o[i] %= p

for i in range(b+1,a):
    for j in range(b,i):
        o[n] += xs0[j] * x[n-i]
        o[i]%=p

ans = o[n] + x[n]
ans %= p

#print(ans)

beki2 = [1]*5001

for i in range(5000):
    beki2[i+1] = beki2[i]*2
    beki2[i+1] %= p

ans = beki2[n] - ans
ans += p
ans %= p

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, A, B = map(int, read().split())

def solve(N, A, B):
    if A > B:
        A, B = B, A
    if A == 1:
        return pow(2, N, MOD)
    dp1 = np.zeros((N, B), dtype=np.int64)  # その時点で確定している長さ集計
    dp2 = np.zeros((N, B), dtype=np.int64)  # もし右に十分な 0 があったとしたときの、長さ集計
    dp1_sum = np.zeros(N, dtype=np.int64)
    ans = 0
    for n in range(N):
        # そこで初めての 1 がたつ場合
        if n < A:
            dp1[n, 1] += 1
        else:
            if n + 1 < B:
                dp1[n, n + 1] += 1
        # ひとつ手前から 1 を立てて遷移した場合
        if n > 0:
            dp1[n, 1:] += dp1[n - 1, :-1]
        # 使えない個数の 0 をはさんで遷移した場合
        dp1[n, 1] += dp1_sum[max(0, n - A):n - 1].sum() % MOD
        # たくさんの個数の 0 をはさんで遷移した場合
        if n >= A + 1 < B:
            dp1[n, A + 1:B] += dp2[n - A - 1, 0:B - (A + 1)]
        dp1[n] %= MOD
        # 右を 0 埋めして足せるなら答に足す
        dp1_sum[n] = dp1[n].sum() % MOD
        if (N - n - 1) < A:
            ans += dp1_sum[n]
        else:
            # あと N - n - 1 のびても B にならないような範囲
            M = B - (N - n - 1)
            if M > 0:
                ans += dp1[n, :M].sum() % MOD
        dp2[n] += dp1[n]
        dp2[n, 1:] += dp2[n - 1, :-1]
        dp2[n] %= MOD
    x = pow(2, N, MOD) - ans
    return x % MOD

print(solve(N, A, B))

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, A, B = map(int, read().split())

def solve(N, A, B):
    if A > B:
        A, B = B, A
    if A == 1:
        return pow(2, N, MOD)
    dp1 = np.zeros((N, B), dtype=np.int64)  # その時点で確定している長さ集計
    dp2 = np.zeros((N, B), dtype=np.int64)  # もし右に十分な 0 があったとしたときの、長さ集計
    dp1_sum = np.zeros(N, dtype=np.int64)
    ans = 0
    for n in range(N):
        # そこで初めての 1 がたつ場合
        if n < A:
            dp1[n, 1] += 1
        else:
            if n + 1 < B:
                dp1[n, n + 1] += 1
        # ひとつ手前から 1 を立てて遷移した場合
        if n > 0:
            dp1[n, 1:] += dp1[n - 1, :-1]
        # 使えない個数の 0 をはさんで遷移した場合
        dp1[n, 1] += dp1_sum[max(0, n - A):n - 1].sum() % MOD
        # たくさんの個数の 0 をはさんで遷移した場合
        if n >= A + 1 < B:
            dp1[n, A + 1:B] += dp2[n - A - 1, 0:B - (A + 1)]
        dp1[n] %= MOD
        # 右を 0 埋めして足せるなら答に足す
        dp1_sum[n] = dp1[n].sum() % MOD
        if (N - n - 1) < A:
            ans += dp1_sum[n]
            ans %= MOD
        else:
            # あと N - n - 1 のびても B にならないような範囲
            M = B - (N - n - 1)
            if M > 0:
                ans += dp1[n, :M].sum() % MOD
        dp2[n] += dp1[n]
        dp2[n, 1:] += dp2[n - 1, :-1]
        dp1[n] %= MOD
        dp2[n] %= MOD
    x = pow(2, N, MOD) - ans
    return x % MOD

print(solve(N, A, B))

Submission status: Runtime Error

Solution code:
S = list(input())
N = int(input())

'''
ordの位置
#z = 122
#a = 97
左の文字からNで'a'に出来るかを確認
aに出来るならaにして使った分をNから引く
繰り返して行き一番最後にあまりをすべて使う'''
  
for i, s in enumerate(S):
  if ord(s) - 97 > 0  and 122 - ord(s) < N:
    S[i] = "a"
    N -= 123 - ord(s)
else:
  S[i] = (chr((ord(S[i]) + N) % 122 ))
  
  
print("".join(S))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, A, B = map(int, read().split())

if A > B:
    A, B = B, A

dp1 = np.zeros((N, B), dtype=np.int64)  # その時点で確定している長さ集計
dp2 = np.zeros((N, B), dtype=np.int64)  # もし右に十分な 0 があったとしたときの、長さ集計
dp1_sum = np.zeros(N, dtype=np.int64)

ans = 0
for n in range(N):
    # そこで初めての 1 がたつ場合
    if n + 1 < B:
        if n >= A:
            dp1[n, n + 1] += 1
        else:
            dp1[n, 1] += 1
    # ひとつ手前から 1 を立てて遷移した場合
    dp1[n, 1:] += dp1[n - 1, :-1]
    dp1[n] %= MOD
    # 使えない個数の 0 をはさんで遷移した場合
    if n >= A:
        dp1[n, 1] += dp1_sum[n - A:n - 1].sum() % MOD
    # たくさんの個数の 0 をはさんで遷移した場合
    if n >= A + 1:
        dp1[n, A + 1:B] += dp2[n - A - 1, 0:B - (A + 1)]
    dp1[n] %= MOD
    # 右を 0 埋めして足せるなら答に足す
    dp1_sum[n] = dp1[n].sum() % MOD
    if (N - n - 1) < A:
        ans += dp1_sum[n]
        ans %= MOD
    else:
        # あと N - n - 1 のびても B にならないような範囲
        M = B - (N - n - 1)
        if M > 0:
            ans += dp1[n, :M].sum() % MOD
    dp2[n] += dp1[n]
    dp2[n, 1:] += dp2[n - 1, :-1]
    dp1[n] %= MOD
    dp2[n] %= MOD

x = pow(2, N, MOD) - ans
print(x % MOD)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, A, B = map(int, read().split())

if A > B:
    A, B = B, A

dp1 = np.zeros((N, B), dtype=np.int64)  # その時点で確定している長さ集計
dp2 = np.zeros((N, B), dtype=np.int64)  # もし右に十分な 0 があったとしたときの、長さ集計
dp1_sum = np.zeros(N, dtype=np.int64)

ans = 0
for n in range(N):
    # そこで初めての 1 がたつ場合
    if n + 1 < B:
        if n >= A:
            dp1[n, n + 1] += 1
        else:
            dp1[n, 1] += 1
    # ひとつ手前から 1 を立てて遷移した場合
    dp1[n, 1:] += dp1[n - 1, :-1]
    dp1[n] %= MOD
    # 使えない個数の 0 をはさんで遷移した場合
    dp1[n, 1] += dp1_sum[n - A:n - 1].sum() % MOD
    # たくさんの個数の 0 をはさんで遷移した場合
    if n >= A + 1:
        dp1[n, A + 1:B] += dp2[n - A - 1, 0:B - (A + 1)]
    dp1[n] %= MOD
    # 右を 0 埋めして足せるなら答に足す
    dp1_sum[n] = dp1[n].sum() % MOD
    if (N - n - 1) < A:
        ans += dp1_sum[n]
        ans %= MOD
    else:
        # あと N - n - 1 のびても B にならないような範囲
        M = B - (N - n - 1)
        if M > 0:
            ans += dp1[n, :M].sum() % MOD
    dp2[n] += dp1[n]
    dp2[n, 1:] += dp2[n - 1, :-1]
    dp1[n] %= MOD
    dp2[n] %= MOD

x = pow(2, N, MOD) - ans
print(x % MOD)