Problem:


Score : 900 points

Problem Statement

Joisino has a lot of red and blue bricks and a large box.
She will build a tower of these bricks in the following manner.

First, she will pick a total of N bricks and put them into the box.
Here, there may be any number of bricks of each color in the box, as long as there are N bricks in total.
Particularly, there may be zero red bricks or zero blue bricks.
Then, she will repeat an operation M times, which consists of the following three steps:

Take out an arbitrary brick from the box.

Put one red brick and one blue brick into the box.

Take out another arbitrary brick from the box.

After the M operations, Joisino will build a tower by stacking the 2 \times M bricks removed from the box, in the order they are taken out.
She is interested in the following question: how many different sequences of colors of these 2 \times M bricks are possible?
Write a program to find the answer.
Since it can be extremely large, print the count modulo 10^9+7.

Constraints

1 \leq N \leq 3000

1 \leq M \leq 3000

Input

Input is given from Standard Input in the following format:

N M

Output

Print the count of the different possible sequences of colors of 2 \times M bricks that will be stacked, modulo 10^9+7.

Sample Input 1

2 3

Sample Output 1

56

A total of six bricks will be removed from the box. The only impossible sequences of colors of these bricks are the ones where the colors of the second, third, fourth and fifth bricks are all the same. Therefore, there are 2^6 - 2 \times 2 \times 2 = 56 possible sequences of colors.

Sample Input 2

1000 10

Sample Output 2

1048576

Sample Input 3

1000 3000

Sample Output 3

693347555



Sample input:
2 3


Sample output:
56

Submission status: Time Limit Exceeded

Solution code:


MOD = int(1e9 + 7)
n, m = map(int, raw_input().split())

dp = [[[0, 0] for _ in range(n + 1)] for _ in range(m + 1)]  #dp[i][j][k]: i operaciones j rojas en la caja haciendo k operaciones especiales

for i in range(n + 1):
    dp[0][i][0] = 1

for i in range(m):
    for j in range(n + 1):
        for k in range(2):
            if dp[i][j][k]:
                if j > 0:
                    # RR
                    if j == 1:
                        dp[i + 1][j - 1][1] = (dp[i + 1][j - 1][1] + dp[i][j][k]) % MOD
                    else:
                        dp[i + 1][j - 1][k] = (dp[i + 1][j - 1][k] + dp[i][j][k]) % MOD

                    # RB
                    if j == 1:
                        dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][k]) % MOD
                    else:
                        dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD

                if j < n:
                    # BB
                    if j == 0:
                        dp[i + 1][j + 1][1] = (dp[i + 1][j + 1][1] + dp[i][j][k]) % MOD
                    else:
                        dp[i + 1][j + 1][k] = (dp[i + 1][j + 1][k] + dp[i][j][k]) % MOD

                    # BR
                    if j == 0:
                        dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][k]) % MOD
                    else:
                        dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD

resp = 0
for i in range(n + 1):
    resp += dp[m][i][1]
    resp %= MOD

print resp

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
temp=input().split()
N=int(temp[0])
M=int(temp[1])
INF=10**9+7
#Ans=0
#動的計画法で解きます
#dp1は、[not goto 0, already 0]の場合の数とする。
#dp=[[0 for j in range(N+1)] for i in range(2*M+1)]
dp1=[[0 for j in range(N+1)]]
dp2=[[0 for j in range(N+1)]]
dp2[0][0]=1
for i in range(1,N+1):
	dp1[0][i]=1
#少しずつ下に進めていきます
for i in range(2*M):
	#偶数回目の取り出す場合
	if i%2==0:
		dp1+=[[x+y for(x,y) in zip(dp1[i][0:N],dp1[i][1:N+1])]+[0]]
		dp2+=[[x+y for(x,y) in zip(dp2[i][0:N],dp2[i][1:N+1])]+[0]]
		dp2[i+1][0]+=dp1[i+1][0]
		dp1[i+1][0]=0
	#奇数回目の取り出す場合（取り出さないことを+1として考えます）
	else:
		dp1+=[[0]+[x+y for(x,y) in zip(dp1[i][0:N],dp1[i][1:N+1])]]
		dp2+=[[dp2[i][0]]+[x+y for(x,y) in zip(dp2[i][0:N],dp2[i][1:N+1])]]
	for j in range(N+1):
		dp1[i+1][j]%=INF
		dp2[i+1][j]%=INF
ans=0
for j in range(N+1):
	ans+=dp2[2*M][j]
print(ans%INF)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#import time
#start=time.time()
temp=input().split()
N=int(temp[0])
M=int(temp[1])
INF=10**9+7
#Ans=0
#動的計画法で解きます
#dp1は、[not goto 0, already 0]の場合の数とする。
#dp=[[0 for j in range(N+1)] for i in range(2*M+1)]
def DP():
	dp1=[[0 for j in range(N+1)]]
	dp2=[[0 for j in range(N+1)]]
	dp2[0][0]=1
	for i in range(1,N+1):
		dp1[0][i]=1
	ans=0
	all=0
	#少しずつ下に進めていきます
	for i in range(2*M):
		dp1+=[[x+y for(x,y) in zip(dp1[i][0:N],dp1[i][1:N+1])]]
		dp2+=[[x+y for(x,y) in zip(dp2[i][0:N],dp2[i][1:N+1])]]
		#偶数回目の取り出す場合
		if i%2==0:
			dp2[i+1][0]+=dp1[i+1][0]
			dp1[i+1][0]=0
			dp1[i+1]+=[0]
			dp2[i+1]+=[0]
		#奇数回目の取り出す場合（取り出さないことを+1として考えます）
		else:
			dp1[i+1].insert(0,0)
			dp2[i+1].insert(0,dp2[i][0])
		for j in range(N+1):
			dp1[i+1][j]%=INF
			dp2[i+1][j]%=INF
	for j in range(N+1):
		ans+=dp2[2*M][j]
	return ans

all=DP()
#end=time.time()
print(all%INF)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
temp=input().split()
N=int(temp[0])
M=int(temp[1])
INF=10**9+7
Ans=0
#動的計画法で解きます
#dp1は、[not goto 0, already 0]の場合の数とする。
#dp=[[0 for j in range(N+1)] for i in range(2*M+1)]
dp1=[[[0,0] for j in range(N+1)] for i in range(2*M+1)]
"""
def DP0():
	ans=0
	#少しずつ下に進めていきます
	for i in range(2*M):
		#偶数回目の取り出す場合
		if i%2==0:
			for j in range(N+1):
				dp[i+1][j]+=dp[i][j]
				if j!=0:
					dp[i+1][j-1]+=dp[i][j]
		#奇数回目の取り出す場合（取り出さないことを+1として考えます）
		else:
			for j in range(N+1):
				dp[i+1][j]+=dp[i][j]
				if j!=N:
					dp[i+1][j+1]+=dp[i][j]
		for j in range(N+1):
			dp[i+1][j]%=INF
	ans=sum(dp[i+1])%INF
	for i in range(2*M+1):
		pass
		#print(dp[i])
	#print(ans)
	return ans
"""
def DP1():
	ans=0
	#少しずつ下に進めていきます
	for i in range(2*M):
		#print(i)
		#偶数回目の取り出す場合
		if i%2==0:
			"""
			#0に行く場合の処理
			dp1[i+1][0][1]+=dp1[i][0][1]+dp1[i][1][0]+dp1[i][1][1]
			dp1[i+1][1][0]+=dp1[i][1][0]
			dp1[i+1][1][1]+=dp1[i][1][1]
			"""
			for j in range(N+1):
				dp1[i+1][j]=dp1[i][j]
				if 0<j:
					dp1[i+1][j-1][0]+=dp1[i][j][0]
					dp1[i+1][j-1][1]+=dp1[i][j][1]
			dp1[i+1][0][1]+=dp1[i+1][0][0]
			dp1[i+1][0][0]=0
			dp1[i+1][N]=[0,0]
		#奇数回目の取り出す場合（取り出さないことを+1として考えます）
		else:
			for j in range(N+1):
				if j!=N:
					dp1[i+1][j+1]=dp1[i][j]
				dp1[i+1][j][0]+=dp1[i][j][0]
				dp1[i+1][j][1]+=dp1[i][j][1]
		for j in range(N+1):
			dp1[i+1][j][0]%=INF
			dp1[i+1][j][1]%=INF
	for j in range(N+1):
		ans+=dp1[2*M][j][1]
	return ans

dp1[0][0][1]=1
for i in range(1,N+1):
	dp1[0][i][0]=1
Ans=DP1()
Ans%=INF
print(Ans)

Submission status: Accepted

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

import numpy as np

MOD = 10 ** 9 + 7

N,M = map(int,input().split())

# 1度は赤が0個になるような初期状態だけを考える
# 箱の状態、0個を経由したか否か
dp_T = np.zeros(N+1, dtype=np.int64)
dp_F = np.ones_like(dp_T)
dp_T[0] = 1
dp_F[0] = 0

for _ in range(M):
    prev_T = dp_T
    prev_F = dp_F
    dp_T = np.zeros_like(prev_T)
    dp_F = np.zeros_like(prev_F)
    # 赤赤
    dp_T[0:-1] += prev_T[1:]
    dp_F[1:-1] += prev_F[2:]
    dp_T[0] += prev_F[1]
    # 赤青
    dp_T[1:] += prev_T[1:]
    dp_F[2:] += prev_F[2:]
    dp_T[1] += prev_F[1]
    # 青赤
    dp_T[:-1] += prev_T[:-1]
    dp_F[:-1] += prev_F[:-1]
    # 青青
    dp_T[1:] += prev_T[:-1]
    dp_F[1:] += prev_F[:-1]
    
    dp_T %= MOD
    dp_F %= MOD

answer = dp_T.sum() % MOD
print(answer)