Problem Statement
题目大意是给定一个N*M的棋盘，然后棋盘上染色，要求染色满足这样的条件，染色块的四领域内的染色块数为偶数。
用dp[i][j][k]表示1..i行，第i行放置状态为j，奇偶性为k的方案数，用f[i][j][k]表示放置状态为j，奇偶性对应为k的方案数，其中判断奇偶性时用到二进制处理，最后的复杂度为O(N*4^M)，
内存方面要用滚动数组优化，解题报告的做法是用三进制，本来没用到f[i][j][k]，实现了一个O(N*8^M)的算法，就是在状态转移的时候又枚举了一下，这样在TC上会超时，
用了一个中间数组f存储了中间结果，并优化下存储就可以了~
using namespace std;#include <iostream>using namespace std;const int M = 1000000007;typedef long long int64;int64 dp[2][1 << 8][1 << 8], f[2][1 << 8][1 << 8];class DengklekPaintingSquares{public:int numSolutions(int m, int n) { memset(dp, 0, sizeof(dp)); memset(f, 0, sizeof(f)); dp[0][0][0] = 1; f[0][0][0] = 1;for(int i = 1; i <= m + 1; i++) { memset(dp[i & 1], 0, sizeof(dp[i & 1])); memset(f[i & 1], 0, sizeof(f[i & 1]));for(int j = 0; j < (1 << n); j++) {for(int k = 0; k < (1 << n); k++) {int dj = (j >> 1) ^ ((j << 1) & ((1 << n) - 1)) ^ k; dp[i & 1][j][k] += f[(i + 1) & 1][dj][dj & j]; dp[i & 1][j][k] %= M; f[i & 1][j][j & k] += dp[i & 1][j][k]; f[i & 1][j][j & k] %= M; } } }return f[(m + 1) & 1][0][0]; }};转载于:https://www.cnblogs.com/litstrong/archive/2012/02/23/2364940.html
相关资源：数据结构—成绩单生成器