【HIHOCODER 1048】状态压缩·二

描述

历经千辛万苦，小Hi和小Ho终于到达了举办美食节的城市！虽然人山人海，但小Hi和小Ho仍然抑制不住兴奋之情，他们放下行李便投入到了美食节的活动当中。美食节的各个摊位上各自有着非常多的有意思的小游戏，其中一个便是这样子的：

小Hi和小Ho领到了一个大小为NM的长方形盘子，他们可以用这个盒子来装一些大小为21的蛋糕。但是根据要求，他们一定要将这个盘子装的满满的，一点缝隙也不能留下来，才能够将这些蛋糕带走。

这么简单的问题自然难不倒小Hi和小Ho，于是他们很快的就拿着蛋糕离开了~

但小Ho却不只满足于此，于是他提出了一个问题——他们有多少种方案来装满这个N*M的盘子呢？

值得注意的是，这个长方形盘子的上下左右是有区别的，如在N=4, M=3的时候，下面的两种方案被视为不同的两种方案哦！

提示：我们来玩拼图吧！不过不同的枚举方式会导致不同的结果哦！

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第一行为两个正整数N、M，表示小Hi和小Ho拿到的盘子的大小。

对于100%的数据，满足2<=N<=1000, 3<=m<=5。<>

输出

考虑到总的方案数可能非常大，只需要输出方案数除以1000000007的余数。

样例输入

2 4

样例输出

题解

dp[i][status]代表考虑第i行，status设为2*m位,0~m-1位为当前行状态，m~2*m-1为下一行状态

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD=(int)1e9+7;  
    static int dp[][]=new int[2][1027];
    public static void main(String[] args) {  
        InputStream sys=System.in;
        InputReader in=new InputReader(sys);
        PrintWriter out=new PrintWriter(System.out);
    	int n=in.nextInt(),m=in.nextInt();  
        int full = (1 << m) - 1;  
        int status = (1 << 2*m);  
        dp[0][0] = 1;  int cur=1;
        for(int i = 0; i < n; i++) { 
        	cur^=1; 
            for(int k = 0; k < m; k++) {
                for(int j = 0; j < status; j++) {
                    if((j & (1 << k)) == 0) {
                    	//竖着放
                        dp[cur][j | (1 << k) | (1 << (k + m))] += dp[cur][j];
                        dp[cur][j | (1 << k) | (1 << (k + m))] %= MOD;
                        //横着放
                        if(k + 1 < m && (j & (1 << (k + 1))) == 0) {
                            dp[cur][j | (1 << k) | (1 << (k + 1))] += dp[cur][j];
                            dp[cur][j | (1 << k) | (1 << (k + 1))] %= MOD; 
                        }  
                    }  
                }  
            }  
            for(int j= 0; j < status; j++) dp[cur^1][j]=0;
            for(int j = 0; j < status; j++) {
                if(j >= full) {  
                    dp[cur^1][j >> m] = dp[cur][j];  
                }  
            }
        } 
        out.printf("%d
", dp[cur][full]);
        out.flush();
    }  

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}