Problem:


Score : 700 points

Problem Statement

Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.

Iroha is looking for X,Y,Z-Haiku (defined below) in integer sequences.

Consider all integer sequences of length N whose elements are between 1 and 10, inclusive. Out of those 10^N sequences, how many contain an X,Y,Z-Haiku?

Here, an integer sequence a_0, a_1, ..., a_{N-1} is said to contain an X,Y,Z-Haiku if and only if there exist four indices x, y, z, w (0 ≦ x < y < z < w ≦ N) such that all of the following are satisfied:

a_x + a_{x+1} + ... + a_{y-1} = X

a_y + a_{y+1} + ... + a_{z-1} = Y

a_z + a_{z+1} + ... + a_{w-1} = Z

Since the answer can be extremely large, print the number modulo 10^9+7.

Constraints

3 ≦ N ≦ 40

1 ≦ X ≦ 5

1 ≦ Y ≦ 7

1 ≦ Z ≦ 5

Input

The input is given from Standard Input in the following format:

N X Y Z

Output

Print the number of the sequences that contain an X,Y,Z-Haiku, modulo 10^9+7.

Sample Input 1

3 5 7 5

Sample Output 1

1

Here, the only sequence that contains a 5,7,5-Haiku is [5, 7, 5].

Sample Input 2

4 5 7 5

Sample Output 2

34

Sample Input 3

37 4 2 3

Sample Output 3

863912418

Sample Input 4

40 5 7 5

Sample Output 4

562805100



Sample input:
3 5 7 5


Sample output:
1

Submission status: Wrong Answer

Solution code:
def comb(a,b):
    if b == 0 or b == a:
        ret = 1
    else:
        ret = 1
        for i in range(a-b+1,a+1):
            ret *= i
        for i in range(1,b+1):
            ret //= i
    return ret

def use575(s,x,y,z,m = 10**9+7):
    ans = 0
    for i in range(1,x+1):
        for j in range(1,y+1):
            if 1 <= s-i-j <= z:
                k = s-i-j
                ans += comb(x-1,i-1)*comb(y-1,j-1)*comb(z-1,k-1)
                #print(i,j,k,ans)
                #print(comb(x-1,i-1),comb(y-1,j-1),comb(z-1,k-1))
                ans %= m
    return ans

n, a, b, c = [ int(v) for v in input().split() ]
mod = 10**9+7
notuse575 = []

t = 1
for i in range(1,41):
    notuse575.append((t*i)%mod)
    t = ( t * 10 ) % mod

ans = 0
for i in range(n-2):
    # print(n-i)
    # print(notuse575[i], use575(n-i,a,b,c))
    ans += notuse575[i] * use575(n-i,a,b,c)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
n, x, y, z = map(int,input().split())
xyz = 2**(x+y+z-1) + 2**(y+z-1) + 2**(z-1)
w = 2**(x+y+z-1)
dp = [[0]*w for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(w):
        for k in range(1,11):
            nj = ((j+j+1)<<(k-1))
            if nj&xyz != xyz:
                dp[i+1][nj%w] = (dp[i+1][nj%w]+dp[i][j])%mod

print(dp)
print((pow(10,n,mod)-sum(dp[-1])%mod)%mod)

Submission status: Wrong Answer

Solution code:
n,x,y,z = map(int,input().split())
mod = 10**9+7

def judge(s):
    sx = 0
    px = -1
    for i in range(len(s)-1,-1,-1):
        sx += int(s[i])
        if sx == x:
            px = i
            break
    if px == -1:
        return True
    
    sy = 0
    py = -1
    for i in range(px-1,-1,-1):
        sy += int(s[i])
        if sy == y:
            py = i
            break
    if py == -1:
        return True
    
    sz = 0
    for i in range(py-1,-1,-1):
        sz += int(s[i])
        if sz == z:
            return False
    return True

d = [{},{'':1}]
sample = ('1','2','3','4','5','6','7','8')

for i in range(n):
    d[i%2] = {}
    for plus in sample:
        for e in d[(i+1)%2]:
            if judge(e+plus):

                a = e+plus
                s = 0
                for elt in a:
                    s += int(elt)
                ind = 0
                while s >= x+y+z:
                    s -= int(a[ind])
                    ind += 1
                
                ind2 = -1
                for j in range(len(a)-1,ind-1,-1):
                    if int(a[j]) > z:
                        ind2 = j
                        break
                new = a[max(ind,ind2):]

                pl = d[(i+1)%2][e]
                if plus == '8':
                    pl = pl*3%mod
                if new in d[i%2]:
                    d[i%2][new] = (d[i%2][new]+pl)%mod
                else:
                    d[i%2][new] = pl

res = 0
for e in d[(n+1)%2].values():
    res = (res+e)%mod
print((pow(10,n,mod)-res)%mod)

Submission status: Wrong Answer

Solution code:
N, X, Y, Z = [int(_) for _ in input().split()]
mod = 10**9 + 7
dp = [0] * (2**(X + Y + Z))
al = (2**(X + Y + Z)) - 1
for i in range(1, 11):
    if i - 1 < X + Y + Z:
        dp[1 << (i - 1)] = 1
ng = (2**Z + 2**(Y + Z) + 2**(X + Y + Z)) // 2
for _ in range(N - 1):
    dpn = [0] * (2**(X + Y + Z))
    for i in range(1, 11):
        for b in range(2**(X + Y + Z)):
            nb = (b << i | 1 << (i - 1)) & al
            if ng & nb == ng:
                continue
            dpn[nb] += dp[b]
            dpn[nb] %= mod
    dp = dpn
ans = 10**N - sum(dp)
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
show_flg=True

n,X,Y,Z=MI()
t=2**16
dp=[0]*t
dp[0]=1

for i in range(n):
    tm=[i for i in dp]
    for k in range(t):
        for d in range(1,10):
            m=bin(k)[2:]+'1'+'0'*(d-1)
            if len(m)>=X+Y+Z and (m[-Z],m[-Y-Z],m[-X-Y-Z])==(1,1,1):
                continue
            else:
                dp[int(m)%t]+=tm[k]
                dp[int(m)%t]%=mo
sub=0
for i in range(t):
    sub+=dp[i]
ans=pow(10,n,mo)-sub
print(ans%mo)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True


n,X,Y,Z=MI()

pt=[[0]*11 for _ in range(42)]

for m in range(1,42):
    if m==1:
        for a in range(1,11):pt[m][a]=1
        continue
    for a in range(1,8):
        an=0
        for i in range(1,11):
            if a-i>=0:an+=pt[m-1][a-i]
        pt[m][a]=an
    
def cnt(m,a):
    if m==1:
        pt[1][a]=1
        return a
    if pt[m][a]!=-1:
        return pt[m][a]
    rt=0
    for i in range(1,11):
        if a-i<=0:
            break
        rt+=cnt(m-1,a-i)
    pt[m][a]=rt
    return rt

ans=0
for x in range(n+1):
    for y in range(x+1,n+1):
        for z in range(y+1,n+1):
            for w in range(z+1,n+1):
                p=1
                p*=pt[y-x][X]
                p*=pt[z-y][Y]
                p*=pt[w-z][Z]
                ans+=p*pow(10,n-(w-x),mo)
                show(x,y,z,w,p)

print(ans%mo)

Submission status: Wrong Answer

Solution code:
N, X, Y, Z = map(int, input().split())
ans = 0
mod = 10**9 + 7

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


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



for i in range(N+1):
    for j in range(i+1, N+1):
        for k in range(j+1, N+1):
            for l in range(k+1, N+1):
                ans += cmb(X-1, X-(j-i), mod) * cmb(Y-1, Y-(k-j), mod) * cmb(Z-1, Z-(l-k), mod) * 10**(i) * 10**(N-l)
                ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X, Y, Z = MAP()
M = X + Y + Z

# XYZとの一致をチェックするビット列
check = 1<<(X+Y+Z-1) | 1<<(Y+Z-1) | 1<<(Z-1)
dp = list2d(N+1, 1<<(M-1), 0)
# dp[i][S] := i個目まで見て、前の値M-1以下までの集合がSの時の、XYZを含まないものの通り数
dp[0][0] = 1
msk1 = (1<<M) - 1
msk2 = (1<<(M-1)) - 1
for i in range(N):
    for S in range(1<<(M-1)):
        if not dp[i][S]:
            continue
        for j in range(10):
            # 1ビットずらして1を足してjビットずらしてマスクする
            S2 = (S<<1|1)<<j & msk1
            # 直前Mビットで使った値がXYZと一致していないか確認する
            if not (S2 & check) == check:
                dp[i+1][S2&msk2] += dp[i][S]
                dp[i+1][S2&msk2] %= MOD
total = pow(10, N, MOD)
cnt = 0
for S in range(1<<(M-1)):
    cnt += dp[N][S]
    cnt %= MOD
print((total-cnt)%MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y,z = map(int,input().split())
mod = 10**9+7
ma = max(x,y,z)

def f(a):
    s = 0
    for e in a:
        s += int(e)
    ind = 0
    while s >= x+y+z:
        s -= int(a[ind])
        ind += 1
    
    ind2 = -1
    for i in range(len(a)-1,ind-1,-1):
        if int(a[i]) > ma:
            ind2 = i
            break
    return a[max(ind,ind2):]

def judge(s):
    sx = 0
    px = -1
    for i in range(len(s)-1,-1,-1):
        sx += int(s[i])
        if sx == x:
            px = i
            break
    if px == -1:
        return True
    
    sy = 0
    py = -1
    for i in range(px-1,-1,-1):
        sy += int(s[i])
        if sy == y:
            py = i
            break
    if py == -1:
        return True
    
    sz = 0
    for i in range(py-1,-1,-1):
        sz += int(s[i])
        if sz == z:
            return False
    return True

d = [{},{'':1}]
sample = ('1','2','3','4','5','6','7','8')

for i in range(n):
    d[i%2] = {}
    for plus in sample:
        for e in d[(i+1)%2]:
            if judge(e+plus):
                new = f(e+plus)
                pl = d[(i+1)%2][e]
                if plus == '8':
                    pl = pl*3%mod
                if new in d[i%2]:
                    d[i%2][new] = (d[i%2][new]+pl)%mod
                else:
                    d[i%2][new] = pl
res = 0
for e in d[(n+1)%2].values():
    res = (res+e)%mod
print((pow(10,n,mod)-res)%mod)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y, Z = map(int, input().split())
p = 10 ** 9 + 7
m = 1
m <<= X
m += 1
m <<= Y
m += 1
m <<= Z - 1
L = 2 ** (X + Y + Z - 1)
M = [[0 for _ in range(10)] for _ in range(L)]
for i in range(L):
  for j in range(10):
    k =  i << (j + 1)
    k += 1 << j
    M[i][j] = (k % L) if k & m != m else -1
DP = [[0 for _ in range(L)] for _ in range(N + 1)]
DP[0][0] = 1
for i in range(N):
  for j in range(L):
    if DP[i][j] == 0:
      continue
    DP[i][j] %= p
    for k in range(10):
      l = M[j][k]
      if l < 0:
        continue
      DP[i + 1][l] += DP[i][j]
cnt = 10 ** N % p
print((cnt - sum(DP[N]) % p) % p)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, X, Y, Z = map(int, input().split())
MOD = 10 ** 9 + 7

dp = [[0] * (1 << 18) for i in range(N + 1)]

ng = (1 << Z) + (1 << (Y + Z)) + (1 << (X + Y + Z))
S = (1 << (X + Y + Z + 1)) - 1
dp[0][1] = 1
for i in range(N):
    for j in range(S + 1):
        for k in range(1, 11):
            s = ((j << k) & S) + 1
            if s & ng == ng:
                continue
            dp[i + 1][s] += dp[i][j]
            dp[i + 1][s] %= MOD


ans = pow(10, N, MOD)
num = 0
for i in range(S):
    num += dp[N][i]
    num %= MOD

print((ans - num + MOD) % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,X,Y,Z = map(int,read().split())

N = 1<<(X+Y+Z)
NX = 1<<X
NY = 1<<(X+Y)
NZ = 1<<(X+Y+Z)

MX = (1<<X) - 1
MY = (1<<(Y+X)) - (1<<X)
MZ = (1<<(X+Y+Z)) - (1<<(Y+X))

MMX = MX<<1
MMY = MY<<1
MMZ = MZ<<1

dp = [0]*N
dp[1] = 1

MOD = 10**9+7

for _ in range(n):
    ndp = [0]*N
    #cnt = 0
    #bad = 0
    for mask in range(N):
        if dp[mask]==0: continue
        mx = mask&MX
        my = mask&MY
        mz = mask&MZ
        
        for j in range(1,11):
            nmx = mx << j
            nmx &= MMX

            nmy = my << j
            nmy &= MMY

            nmz = mz << j
            nmz &= MMZ

            nmask = nmx|nmy|nmz|1
            if not nmask&(1<<(X+Y+Z)):
                ndp[nmask] += dp[mask]
                ndp[nmask] %= MOD

    dp = ndp
    #print(sum(dp),"sum")

ans = (pow(10,n,MOD)-sum(dp))
print(ans%MOD)

Submission status: Accepted

Solution code:
n, x, y, z = map(int, input().split())
s = x+y+z
MOD = 10**9+7
dp = [[0]*(1<<s) for _ in range(n+1)]
dp[0][0] = 1
mask = (1<<s) - 1
for i in range(n):
  for j in range(1<<s):
    for k in range(1, 11):
      t = ((j<<k) | (1<<(k-1))) & mask
      if t>>(z-1) & 1 and t>>(y+z-1)&1 and t>>(x+y+z-1)&1:
        continue
      dp[i+1][t] += dp[i][j]
      dp[i+1][t] %= MOD
ans = pow(10, n, MOD) - sum(dp[n])
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n, x, y, z = map(int, input().split())
mod = 10 ** 9 + 7
simple_xyz = (1 << (x + y + z - 1)) | (1 << (y + z - 1)) | (1 << (z - 1))
def isnotxyz(b):
    return b & simple_xyz != simple_xyz
dp = [[0] * (1 << (x + y + z - 1)) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for b in range(1 << (x + y + z - 1)):
        if dp[i][b] == 0:
            continue
        for j in range(10):
            # 右から10...0(0はj個)を付け足し、(x + y + z)桁目より左の情報は忘れる
            new_b = ((b << 1 | 1) << j) & ((1 << (x + y + z)) - 1)
            if isnotxyz(new_b):
                new_b &= (1 << (x + y + z - 1)) - 1
                dp[i + 1][new_b] += dp[i][b]
                dp[i + 1][new_b] %= mod
def summod(a, mod):
    res = 0
    for ai in a:
        res += ai
        res %= mod
    return res
#俳句的でないほうの数を求めたので、全体から引く
print((pow(10, n, mod) - sum(dp[n])) % mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
N,X,Y,Z = map(int, input().split())
num = 1<<(X+Y+Z-1)
ng = ((((1<<X)+1)<<Y)+1)<<(Z-1)

dp = [[0]*num for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(1,11):
        for k in range(num):
            K = (k*2+1)<<(j-1)
            if K&ng != ng:
                K &= num-1
                dp[i+1][K] += dp[i][k]
                dp[i+1][K] %= mod

print((10**N%mod-sum(dp[N])%mod)%mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
N,X,Y,Z = map(int, input().split())
Num = 1<<(X+Y+Z-1)
ng = ((((1<<X)+1)<<Y)+1)<<(Z-1)

dp = [[0]*Num for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for k in range(Num):
        for j in range(1,11):
            a = (k<<j)|(1<<(j-1))
            if a&ng != ng:
                a &= Num-1
                dp[i+1][a] += dp[i][k]
                dp[i+1][a] %= mod

print((10**N%mod-sum(dp[N])%mod)%mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
N,X,Y,Z = map(int, input().split())
Num = 1<<(X+Y+Z-1)
ng = ((((1<<X)+1)<<Y)+1)<<(Z-1)

dp = [[0]*Num for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for k in range(Num):
        for j in range(1,11):
            a = (k<<j)|(1<<(j-1))
            if a&ng != ng:
                a &= Num-1
                dp[i+1][a] += dp[i][k]
                dp[i+1][a] %= mod
cnt = 1
for i in range(N):
    cnt *= 10
    cnt %= mod
for x in dp[N]:
    cnt -= x
    cnt %= mod
print(cnt)

Submission status: Accepted

Solution code:
n, x, y, z = map(int,input().split())
mod = 10 ** 9 + 7
forbit = (1<<(x + y + z -1)) + (1<<(y + z -1 )) + (1<<(z -1))
mask = ((1<<(x+y+z)) -1)
l1 = set()
for i in range(mask + 1):
    if i & forbit:
        l1.add(i)
d = [[0] * (mask + 1) for i in range(n + 1)]
d[0][0] = 1
for j in range(n):
    for i in range(mask + 1):
        for k in range(10):
            t = ((i <<(k + 1)) | 1<<k) & mask
            if (t & forbit) == forbit:
                continue
            d[j + 1][t] += d[j][i]
            d[j + 1][t] %= mod
answer = (10 ** n) % mod
for i in range(mask + 1):
    answer -= d[n][i]
    answer %= mod
print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X, Y, Z = MAP()
M = X + Y + Z

# XYZとの一致をチェックするビット列
check = 1<<(X+Y+Z-1) | 1<<(Y+Z-1) | 1<<(Z-1)
dp = list2d(N+1, 1<<(M-1), 0)
# dp[i][S] := i個目まで見て、前の値M-1以下までの集合がSの時の、XYZを含まないものの通り数
dp[0][0] = 1
msk1 = (1<<M) - 1
msk2 = (1<<(M-1)) - 1
for i in range(N):
    for S in range(1<<(M-1)):
        if not dp[i][S]:
            continue
        for j in range(10):
            # 1ビットずらして1を足してjビットずらしてマスクする
            S2 = (S<<1|1)<<j & msk1
            # 直前Mビットで使った値がXYZと一致していないか確認する
            if (S2 & check) != check:
                dp[i+1][S2&msk2] += dp[i][S]
                dp[i+1][S2&msk2] %= MOD
total = pow(10, N, MOD)
print((total-sum(dp[N])%MOD)%MOD)

Submission status: Accepted

Solution code:
def examE(mod):
    N, X, Y, Z = LI()
    L = 2**(X+Y+Z-1)
    XYZ = (1 << (X + Y + Z - 1)) | (1 << (Y + Z - 1)) | (1 << (Z - 1))
    dp = [[0]*L for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(L):
            for k in range(1,11):
                next = (j<<k)|(1<<(k-1))
                if next&XYZ==XYZ:
                    continue
                else:
                    dp[i+1][next%L] += dp[i][j]
                    dp[i + 1][next % L] %=mod
    ans = pow(10,N,mod)-sum(dp[-1])%mod
    if ans<0:
        ans +=mod
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(mod)

Submission status: Accepted

Solution code:
N, X, Y, Z = map(int, input().split())
MOD = 10**9 + 7

# X-Y-Zを含まない数列を数える
D = 2**(X + Y + Z - 1)  # 直前のX+Y+Zビットを保持する

# ビットが立っている部分で数列を区切れる
XYZ = (1 << (X + Y + Z - 1)) | (1 << (Y + Z - 1)) | (1 << (Z - 1))  # X-Y-Z

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

for right in range(N):
    for mask in range(D):
        for nextA in range(1, 11):
            # 110 + 10 = 110 10
            newMask = (mask << (nextA)) | (1 << (nextA - 1))
            if newMask & XYZ != XYZ:  # X-Y-Zを含まない
                dp[right + 1][newMask % D] += dp[right][mask]
                dp[right + 1][newMask % D] %= MOD

ans = pow(10, N, MOD) - sum(dp[-1])
print(ans % MOD)

Submission status: Accepted

Solution code:
mod = 10**9+7
n, x, y, z = map(int,input().split())
xyz = 2**(x+y+z-1) + 2**(y+z-1) + 2**(z-1)
w = 2**(x+y+z-1)
dp = [[0]*w for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(w):
        for k in range(1,11):
            nj = ((j+j+1)<<(k-1))
            if nj&xyz != xyz:
                dp[i+1][nj%w] = (dp[i+1][nj%w]+dp[i][j])%mod

print((pow(10,n,mod)-sum(dp[-1])%mod)%mod)

Submission status: Accepted

Solution code:
N, X, Y, Z = [int(_) for _ in input().split()]
mod = 10**9 + 7
dp = [0] * (2**(X + Y + Z))
dp[0] = 1
al = (2**(X + Y + Z)) - 1
ng = (2**Z + 2**(Y + Z) + 2**(X + Y + Z)) // 2
for _ in range(N):
    dpn = [0] * (2**(X + Y + Z))
    for i in range(1, 11):
        for b in range(2**(X + Y + Z)):
            nb = (b << i | 1 << (i - 1)) & al
            if ng & nb == ng:
                continue
            dpn[nb] += dp[b]
    for b in range(2**(X + Y + Z)):
        dpn[b] %= mod
    dp = dpn
ans = 10**N % mod
ans -= sum(dp)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

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

N,X,Y,Z = II()

max_val = (1<<17)-1
dp = [[0]*(max_val+1) for _ in range(N+1)]

for k in range(1,11):
    dp[1][1<<(k-1)] = 1

for i in range(1,N):
    for j in range(1,max_val+1):
        for k in range(1,11):
            val = ((j<<k) + (1<<(k-1))) & max_val
            if (val>>(Z-1)&1) and (val>>(Z+Y-1)&1) and (val>>(Z+Y+X-1)&1):
                continue
            else:
                dp[i+1][val] += dp[i][j]
                dp[i+1][val] %= mod

temp = 0
for j in range(1,max_val+1):
    temp += dp[N][j]
    temp %= mod

ans = (pow(10,N,mod)-temp)%mod
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,X,Y,Z=MI()
t=1<<(X+Y+Z)
haiku=( (1<<(X+Y+Z)) + (1<<(Y+Z)) + (1<<Z) )>>1
dp=[[0]*t for _ in range(n+1)]
dp[0][0]=1


for i in range(n):
    for k in range(t):
        for d in range(10):
            m=((k<<(d+1))+(1<<d))&(t-1)
            if m&haiku == haiku:
                continue
            else:
                dp[i+1][m]+=dp[i][k]
                dp[i+1][m]%=mo
sub=0
for i in range(t):
    sub+=dp[n][i]
ans=pow(10,n,mo)-sub
print(ans%mo)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,X,Y,Z=MI()
t=1<<(X+Y+Z)
haiku=( (1<<(X+Y+Z)) + (1<<(Y+Z)) + (1<<Z) )>>1
dp=[[0]*t for _ in range(n+1)]
dp[0][0]=1

for i in range(n):
    for k in range(t):
        for d in range(10):
            m=((k<<(d+1))+(1<<d))
            if m&haiku == haiku:
                continue
            else:
                dp[i+1][int(m)%t]+=dp[i][k]
                dp[i+1][int(m)%t]%=mo
sub=0
for i in range(t):
    sub+=dp[n][i]
ans=pow(10,n,mo)-sub
print(ans%mo)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,X,Y,Z=MI()
t=1<<(X+Y+Z)
haiku=( (1<<(X+Y+Z)) + (1<<(Y+Z)) + (1<<Z) )>>1
dp=[0]*t
dp[0]=1


for i in range(n):
    tm=[i for i in dp]
    dp=[0]*t
    for k in range(t):
        for d in range(10):
            m=((k<<(d+1))+(1<<d))
            if m&haiku == haiku:
                continue
            else:
                dp[int(m)%t]+=tm[k]
                dp[int(m)%t]%=mo
sub=0
for i in range(t):
    sub+=dp[i]
ans=pow(10,n,mo)-sub
print(ans%mo)

show(ans,sub)
show(dp)
show(n,t,n*t*10)

Submission status: Accepted

Solution code:
MOD=1000000007

def dfs(total,arr):
    if total==0:
        return [arr]
    ret = []
    for i in range(1,total+1):
        ret += dfs(total-i,arr+[i])
    return ret

N,X,Y,Z=map(int,input().split())
xx,yy,zz=[dfs(n,[]) for n in [X,Y,Z]]

NN=2**(X+Y+Z)
NS=2**(X+Y+Z-1)
isxyz = [False]*NN

for x in xx:
    for y in yy:
        for z in zz:
            tmp=0
            for a in x+y+z:
                tmp = tmp << a
                tmp += (2**(a-1))
            isxyz[tmp]=True
            #print(x+y+z, bin(tmp))

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

mask1=NN-1
mask2=NS-1

for i in range(N):
    for src in range(NS):
        for k in range(1,11):
            if dp[i][src]==0: continue
            state = ((src<<k)+(2**(k-1)))&(mask1)
            
            if isxyz[state] is False:
                dst = state&mask2
                dp[i+1][dst] = (dp[i+1][dst]+dp[i][src])%MOD

ans = 0
for v in dp[N]:
    ans = (ans+v)%MOD
total = (10**N)%MOD
print((total-ans+MOD)%MOD)

Submission status: Accepted

Solution code:
N, X, Y, Z = map(int, input().split())
MOD = 10 ** 9 + 7
ng = (1 << (Z - 1)) + (1 << (Y + Z - 1)) + (1 << (X + Y + Z - 1))
S = (1 << (X + Y + Z)) - 1

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

dp[0][0] = 1
for i in range(1, N + 1):
    for j in range(S + 1):
        for k in range(1, 11):
            s = ((j << k) | 1 << k - 1) & S
            if (s & ng) == ng:
                continue
            dp[i][s] += dp[i - 1][j]
            dp[i][s] %= MOD


ans = pow(10, N, MOD)
num = 0
for i in range(S + 1):
    num += dp[N][i]
    num %= MOD

print((ans - num + MOD) % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N,X,Y,Z = map(int,input().split())

MOD = 10 ** 9 + 7

# ダメなやつを数える
L = max(10,X + Y + Z)
dp = np.zeros(1 << L+1, dtype = np.int64) # 右から見て部分和として踏む場所
rng = np.arange(1 << L+1, dtype=np.int64)
x575 = (1 << Z) + (1 << (Y+Z)) + (1 << (X+Y+Z))
bad = ((x575 & rng) == x575)
dp[1] = 1

for n in range(N):
    prev = dp
    dp = np.zeros_like(prev)
    for i in range(1, 11):
        dp[1::1<<i] += prev.reshape(1<<i, 1<<(L+1-i)).sum(axis = 0)
    dp[bad] = 0
    dp %= MOD

answer = pow(10,N,MOD) - dp.sum()
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
MOD = pow(10, 9) + 7

def main():
  n, x, y, z = map(int, input().split())
  ngnum = pow(2, z-1) + pow(2, y+z-1) + pow(2, x+y+z-1)
  mask = pow(2, x+y+z) - 1
  dp = [[0 for _ in range(mask + 1)] for _ in range(n + 1)]
  ans = 1
  for _ in range(n):
    ans = ans * 10 % MOD

  dp[0][0] = 1
  for i in range(n):
    for j in range(mask + 1):
      if dp[i][j] == 0:
        continue
      for d in range(1, 11):
        t = j*pow(2, d) | pow(2, d-1)
        if (t & ngnum) == ngnum:
          continue
        t &= mask
        dp[i+1][t] = (dp[i+1][t] + dp[i][j]) % MOD

  for i in range(mask + 1):
    ans = (ans + MOD - dp[n][i]) % MOD

  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n,x,y,z = LI()
    po2 = [1<<i for i in range(x+y+z+1)]
    max = po2[x+y+z]
    ng = po2[x+y+z-1]|po2[y+z-1]|po2[z-1]
    dp = [[0 for i in range(max)] for i in range(n+1)]
    dp[0][0] = 1
    mask = max-1
    for i in range(n):
        for j in range(max):
            for k in range(1,11):
                t = j<<k|1<<(k-1)
                if t&ng != ng:
                    t &= mask
                    dp[i+1][t] += dp[i][j]
                    dp[i+1][t] %= mod
    ans = pow(10,n,mod)
    for i in range(max):
        ans -= dp[n][i]
        ans %= mod
    print(ans)


#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
N,X,Y,Z=map(int,input().split())
mod=10**9+7
forbit=(1<<(X+Y+Z -1 )) +(1<<(Y+Z -1 ))+(1<<(Z -1 ))
mask = ((1<<(X+Y+Z)) -1)
dp=[[0]*(mask+1) for i in range(N+1)]
dp[0][0]=1
for n in range(1,N+1):
    for i in range(mask+1):
        for k in range(10):
            t=((i <<(k+1)) | 1<<k) & mask
            if (t & forbit) == forbit:
                continue
            dp[n][t]+=dp[n-1][i]
            dp[n][t]%=mod
ans=pow(10,N,mod)
for i in range(mask+1):
    ans-=dp[N][i]
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
N,X,Y,Z=map(int,input().split())
mod=10**9+7
forbit=(1<<(X+Y+Z -1 )) +(1<<(Y+Z -1 ))+(1<<(Z -1 ))
mask = ((1<<(X+Y+Z)) -1)
s=set()
for i in range(mask+1):
    if i & forbit:
        s.add(i)
dp=[[0]*(mask+1) for i in range(N+1)]
dp[0][0]=1
for n in range(1,N+1):
    for i in range(mask+1):
        #if i in s:
            #continue
        for k in range(10):
            t=((i <<(k+1)) | 1<<k) & mask
            #if t in s:
                #continue
            if (t & forbit) == forbit:
                continue
            dp[n][t]+=dp[n-1][i]
            dp[n][t]%=mod
ans=pow(10,N,mod)
for i in range(mask+1):
    #if i in s:
        #continue
    ans-=dp[N][i]
    ans%=mod
print(ans)