2015
05-23

# Draw and paint

Shadow is interested in the four-color theorem, now he wants to draw some lines on a rectangle paper to divide it into some parts, and then paint these parts with four different colors, the color of two adjacent parts must be different.
Firstly, Shadow draws a horizontal line and divides the paper into two parts (The height and width of two parts must be integer), then he paints one part with a kind of color.
Then he draws a vertical line and divides the other part into two parts (The height and width of two parts must be integer), then he paints one part with a kind of color.
Then he draws a horizontal line……That is to say, Shadow draws a horizontal line during an odd step, and a vertical line during an even step. Shadow repeats these operations until he can’t or doesn’t want to anymore.
Shadow can’t rotate or overturn the paper, do you know how many different ways can he draw lines and paint colors.

The first line is one integer T indicates the number of test cases. (T <= 1000)
Then for each test case, there are two integers n and m ( 0 < n,m <= 40 )in one line, indicates the height and width of the rectangle paper.

The first line is one integer T indicates the number of test cases. (T <= 1000)
Then for each test case, there are two integers n and m ( 0 < n,m <= 40 )in one line, indicates the height and width of the rectangle paper.

3
1 1
1 2
2 1

4
4
16

by—cxlove

http://acm.hdu.edu.cn/listproblem.php?vol=1

7维DP，其实可以优化到6维，横切和竖切的关系在于，旋转之后再切。

dp[x][y][l][r][u][d][k]表示长宽为x,y,上，下，左，右的颜色分别为l,r,u,d时的染色种数，而且与边界的颜色四周不能相同。我们将4种颜色标为1，2，3，4再取空白色为0。当K为0的时候，表示接下来横切，K为1的时候表示接下来竖切。

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 1<<29
#define LL long long
#define MOD 1000000007
using namespace std;
int dp[41][41][5][5][5][5][2];
int get_dp(int x,int y,int l,int r,int u,int d,int k){
if(dp[x][y][l][r][u][d][k]!=-1)
return dp[x][y][l][r][u][d][k];
dp[x][y][l][r][u][d][k]=0;
//处理不能再切的情况
if((x==1&&k==0)||(y==1&&k)){
for(int i=1;i<5;i++)
if(i!=l&&i!=r&&i!=u&&i!=d)
dp[x][y][l][r][u][d][k]++;
return dp[x][y][l][r][u][d][k];
}
dp[x][y][l][r][u][d][k]=0;
if(!k){
for(int i=1;i<x;i++)
for(int j=1;j<5;j++){
if(j!=u&&j!=l&&j!=r)
dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+get_dp(x-i,y,l,r,j,d,1))%MOD;
if(j!=d&&j!=l&&j!=r)
dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+get_dp(i,y,l,r,u,j,1))%MOD;
}
//有t种可能重复，而切的位置有x-1种
int t=0;
for(int i=1;i<=4;i++)
if(i!=u&&i!=l&&i!=r)
for(int j=1;j<=4;j++)
if(j!=d&&j!=l&&j!=r&&j!=i)
t++;
dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+MOD-t*(x-1))%MOD;
//整 个区域都同色
for(int i=1;i<5;i++)
if(i!=l&&i!=r&&i!=u&&i!=d)
dp[x][y][l][r][u][d][k]++;
}
else{
for(int i=1;i<y;i++)
for(int j=1;j<5;j++){
if(j!=l&&j!=d&&j!=u)
dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+get_dp(x,y-i,j,r,u,d,0))%MOD;
if(j!=r&&j!=d&&j!=u)
dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+get_dp(x,i,l,j,u,d,0))%MOD;
}
int t=0;
for(int i=1;i<=4;i++)
if(i!=l&&i!=u&&i!=d)
for(int j=1;j<=4;j++)
if(j!=r&&j!=u&&j!=d&&j!=i)
t++;
dp[x][y][l][r][u][d][k]=(dp[x][y][l][r][u][d][k]+MOD-t*(y-1))%MOD;
for(int i=1;i<5;i++)
if(i!=l&&i!=r&&i!=u&&i!=d)
dp[x][y][l][r][u][d][k]++;
}
return dp[x][y][l][r][u][d][k]%MOD;
}
int main(){
memset(dp,-1,sizeof(dp));
int t;
scanf("%d",&t);
while(t--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",get_dp(x,y,0,0,0,0,0));
}
return 0;
}