Lego Blocks

                            Solution in C :

In C++ :





#include <iostream>

using namespace std;


#define MOD  1000000007

typedef unsigned long long ull;

ull dp[1001]; // with rep
ull dpr1[1001]; // with rep
ull dpr2[1001]; // with rep


ull poww ( ull x, int n){
	if(n==0) return 1;
	ull t = poww(x, n/2);
	t = t * t;
	if(t>=MOD) t%= MOD;
	if(n&1){	
		t = t * x;
		if(t>=MOD) t%= MOD;
	}
	return t;
} 

void pre(){
	dp[1] = 1; dp[2] = 2; dp[3] = 4; dp[4] = 8; 
	for(int i=5;i<=1000;i++){
		dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4];
		if(dp[i] >= MOD)
			dp[i] %= MOD;
	}
}

ull calc(int N, int M){
	for(int i=1;i<=N;i++){
		dpr1[i] = poww(dp[i], M);
	}
	for(int i=1;i<=N;i++){
		dpr2[i] = dpr1[i];
		for(int k=1;k<i;k++){
			ull x = dpr2[k];
			x = x * dpr1[i-k];
			if(x >= MOD)
				x %= MOD;
			dpr2[i] -= x;
			if(dpr2[i] >= MOD)
				dpr2[i] += MOD;
		}
	}
	return dpr2[N];
}

int main(){
	pre();
	int T; 
	int N,M;
	cin >> T;
	while(T--){
		cin >> N >> M;
		cout << calc(M,N) << endl;
		//cout << dp[N][M] << endl;
	}
}








In Java :





import java.util.*;

public class Solution {
	int md=1000000007;
	int[][] ways = new int[1001][1001];
	int[][] waysRestrict = new int[1001][1001];
	public Solution(){
		for(int[] w : ways) Arrays.fill(w, -1);
		for(int[] w : waysRestrict) Arrays.fill(w, -1);
	}
	public int solve(int n, int m)
	{
		if (ways[n][m] != -1) return ways[n][m];
		long ans;
		if (m==1) ans = 1;
		else if (n==1){
			if (m<=4) {
				ans = 2*solve(1,m-1);
			}
			else {
				ans = solve(1,m-1);
				ans = (ans + solve(1,m-2))%md;
				ans = (ans + solve(1,m-3))%md;
				ans = (ans + solve(1,m-4))%md;
			}
		}
		else{
			ans = 1; int one = solve(1,m);
			for (int i=0; i<n; i++) ans = (ans * one)%md;
		}
		ways[n][m] = (int)ans;
		return ways[n][m];
	}
	public int solveRestrict(int n, int m)
	{
		if (waysRestrict[n][m] != -1) return waysRestrict[n][m];
		long ans;
		if (m==1) ans = 1;
//		else if (n==1) ans = solve(n,m);
		else {
			ans = solve(n,m);
			for (int i=1; i<m; i++) {
				long a = solve(n,i);
				a = (a*solveRestrict(n,m-i))%md;
				ans -= a;
				if (ans<0) ans+=md;
			}
		}
		waysRestrict[n][m] = (int)ans;
		return waysRestrict[n][m];
	}
	public static void main (String[] args) {
		Solution o = new Solution();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i=0; i<n; i++) {
			int a, b;
			a = sc.nextInt(); b = sc.nextInt();
			System.out.println(o.solveRestrict(a,b));
		}
		sc.close();
	}
}








In C :





#include<stdio.h>

unsigned long long  int call(int,int);
unsigned long long  int  f[1001];
unsigned long long  int to[1001][1001];
unsigned long long  int res[1001][1001];
int main()
{
int h,w,i,j,t;
unsigned long long  int r=0;
f[1]=1;
f[2]=2;
f[3]=4;
f[4]=8;
for(i=1;i<=1000;i++)
{
for(j=1;j<=1000;j++)
{
    res[i][j]=0;
}
}
for(i=5;i<=10000;i++)
{
f[i]=((f[i-4]+f[i-3])%1000000007+(f[i-2]+f[i-1])%1000000007)%1000000007;
}
for(j=1;j<=1000;j++)
{
to[1][j]=f[j];
}
for(i=2;i<=1000;i++)
{
for(j=1;j<=1000;j++)
{
to[i][j]=(to[i-1][j]*f[j])%1000000007;
}
}

scanf("%d",&t);
while(t--)
{
scanf("%d %d",&h,&w);
//printf("f[%d] = %llu\n",w,f[w]);
r=call(h,w);
printf("%llu\n",r);
}
return 0;
}

unsigned long long  int call(int h,int w)
{
int i=0;
unsigned long long  int r=0;
if(h==1)
{
if(w>4)
return 0;
else
return 1;
}
else if(res[h][w]!=0)
{
return res[h][w];
}
else
{
for(i=1;i<=w-1;i++)
{
r=(r+(call(h,i)*to[h][w-i])%1000000007)%1000000007;
}
if(to[h][w]>r)
r=to[h][w]-r;
else
{
r=r-to[h][w];
r=1000000007-r;  
}
res[h][w]=r;
return res[h][w];
}
}








In Python3 :





m = 1000000007
dp1 = [1,1,2,4]
for i in range(4,1001):
    dp1.append((dp1[-1]+dp1[-2]+dp1[-3]+dp1[-4])%m)
    
def f(h,w):
    dp2 = []
    dp3 = [pow(dp1[i],h,m) for i in range(w+1)]
    for i in range(w+1):
        tmp = dp3[i]
        for j in range(1,i):
            tmp = (tmp - dp2[j]*dp3[i-j])%m
        dp2.append(tmp)
    return dp2[-1]


for e in range(int(input())):
    print(f(*list(map(int,input().split()))))