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: Accepted

Solution code:
N,x,y,z=map(int,input().split())
mask=2**(x+y+z)-1
mod=10**9+7
ng=2**(x+y+z-1)+2**(y+z-1)+2**(z-1)
dp=[[0 for i in range(mask+1)] for i in range(N+1)]
dp[0][0]=1
for i in range(N):
  for j in range(mask+1):
    for k in range(1,11):
      if (mask&((j<<k)+(1<<(k-1))))&ng!=ng:
        dp[i+1][mask&((j<<k)+(1<<(k-1)))]+=dp[i][j]
      dp[i+1][j]%=mod
ans=(10**N)%mod
for j in range(mask+1):
  ans-=dp[N][j]
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
def nextb(b,k):
    b <<= 1
    b += 1
    b <<= k-1
    return b

mod = 10**9+7
N, x, y, z = inpl()
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 = nextb(j,k)
            if nj&xyz != xyz:
                dp[i+1][nj%W] = (dp[i+1][nj%W]+dp[i][j])%mod
print((10**N%mod-sum(dp[-1])%mod)%mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

pow2_XYZ = 2 ** (X + Y + Z)

# flg[hist]: 履歴がhistのとき、XYZを含むかどうか
flg = [False] * pow2_XYZ
mask = ((((1 << X) + 1) << Y) + 1) << (Z - 1)
for hist in range(pow2_XYZ):
    if hist & mask == mask:
        flg[hist] = True

# h2s[hist]: DPでの遷移先
h2s = [[0] * 10 for i in range(pow2_XYZ)]
for hist in range(pow2_XYZ):
    for A in range(1, 11):
        h2s[hist][A - 1] = ((hist << A) + (1 << (A-1))) % pow2_XYZ

# dp[i][hist]: 長さiの、履歴がhistである、XYZを含まない数列の数
dp = [[0] * pow2_XYZ for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for hist in range(pow2_XYZ):
        if dp[i][hist] == 0: continue

        for A in range(1, 11):
            h2 = h2s[hist][A - 1]
            if not flg[h2]:
                dp[i + 1][h2] += dp[i][hist]

    dp[i + 1] = list(map(lambda x: x % MOD, dp[i + 1]))

num = sum(dp[N]) % MOD
print((10 ** N - num) % MOD)

Submission status: Accepted

Solution code:
# seishin.py
N, X, Y, Z = map(int, input().split())
m = 2**(X+Y+Z)
S = [0]*m

L = max(X, Y, Z)

ss = set()
tt = set()

Z0 = (1 << (Z-1))
Y0 = (1 << (Z+Y-1))
X0 = (1 << (X+Z+Y-1))

for i in range(m):
    if i & Z0 and i & Y0 and i & X0:
        ss.add(i)

MASK = 2**(X+Y+Z)-1
MOD = 10**9 + 7

S[0] = 1
for i in range(N):
    T = [0]*m
    for s in range(m):
        if s in ss:
            # XYZが成立
            continue
        b = (s << 1) | 1
        for k in range(1, L+1):
            t = (b << (k-1)) & MASK
            T[t] = (T[t] + S[s]) % MOD
        for k in range(L+1, 11):
            T[0] = (T[0] + S[s]) % MOD
    S = T
ans = 0
for s in range(m):
    if s in ss:
        continue
    ans = (ans + S[s]) % MOD
ans = (pow(10, N, MOD) + MOD - ans) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,x,y,z=map(int,input().split())
mod=10**9+7
mask=1<<(x+y+z-1)
dp=[[0 for i in range(mask+1)] for j in range(n+1)]
dp[0][0]=1
ng=(1<<(x+y+z-1))|(1<<(y+z-1))|(1<<(z-1))
for i in range(n):
    dp[i+1][mask]=(dp[i][mask]*10)%mod
    for j in range(mask):
        for k in range(1,11):
            nmask=(j<<k)|(1<<(k-1))
            if nmask&ng==ng:
                nmask=mask
            else:
                nmask&=mask-1
            dp[i+1][nmask]=(dp[i+1][nmask]+dp[i][j])%mod
print(dp[n][mask])

Submission status: Accepted

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

Submission status: Runtime Error

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

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]*(1<<l) 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):
            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 = 0
for x in dp[N]:
    cnt += x
    cnt %= mod
print((10**N%mod-cnt)%mod)

Submission status: Runtime Error

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]*(1<<l) 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):
            a = (k<<j)|(1<<(j-1))
            if a&ng != ng:
                a &= Num-1
                dp[i+1][a] += dp[i][k]
                dp[i+1][1] %= mod
print((10**N-sum(dp[N]))%mod)

Submission status: Runtime Error

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(11)]

for m in range(1,8):
    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: Runtime Error

Solution code:
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=2050;
//ここまでテンプレ
int main(){
	int N,X,Y,Z;
	cin>>N>>X>>Y>>Z;
	//DP[見ている文字][直前の状態]=その状態になる数列の数
	ll DP[41][1<<17]={};
	DP[0][0]=1;
	for(int i=0;i<N;i++){
		for(int j=0;j<(1<<17);j++){
			//1から10までの数列で、入れてもいいものを探す
			for(int k=1;k<=10;k++){
				//cout<<DP[i][j]<<endl;
				//X+Y+Z-k-1bit目、Y+Z-k-1bit目、Z-k-1bit目がすべて1になっているなら、kを入れてはいけない
				if(Z!=k && j&(1<<(X+Y+Z-k-1)) && j&(1<<(Y+Z-k-1)) && j&(1<<(Z-k-1)))
					continue;
				//Z==kのときは、Z-k-1bit目が立っている必要はない
				if(Z==k && j&(1<<(X+Y+Z-k-1)) && j&(1<<(Y+Z-k-1)))
					continue;
				//そうでないなら、kを入れてもいいので入れる
				int temp=(j<<k)|(1<<k-1);
				//16bit目までを取り出す
				int next=0;
				for(int l=0;l<17;l++)
					if(temp&(1<<l))
						next|=(1<<l);
				DP[i+1][next]+=DP[i][j];
				DP[i+1][next]%=MOD;
			}
		}
	}
	ll ans=0;
	for(int i=0;i<(1<<17);i++){
		ans+=DP[N][i];
		ans%=MOD;
	}
	ll ALL=1;
	for(int i=0;i<N;i++){
		ALL*=10;
		ALL%=MOD;
	}
	cout<<(ALL+MOD-ans)%MOD<<endl;
	return 0;
}