2014
11-05

# Board Coloring

HH is painting a board of size 4 * N. You can assume the color of square (X, Y) on the board is Ax,y which is an integer between 0 and 255. For the beauty of the board, HH decide to paint the board following the rules :
1) Ax,y >= Ax,y-1.
2) For some given pairs of (X1, Y1) (X2, Y2), AX1,Y1 = AX2,Y2
Your task is to calculate how many ways there are to paint the board.

There are multiple test cases, the first line of input contains a single integer denoting the number of test cases.
For each test case, the first line contains an integer N and M, denoting the length of the board and the number of additional rules. (1 <= N <= 15, 0 <= M <= 100)
For next M lines, each line contains four integers X1, Y1, X2, Y2 denoting one additional rule for the painting. (1 <= X1, X2 <= 4, 1 <= Y1, Y2 <= N)

There are multiple test cases, the first line of input contains a single integer denoting the number of test cases.
For each test case, the first line contains an integer N and M, denoting the length of the board and the number of additional rules. (1 <= N <= 15, 0 <= M <= 100)
For next M lines, each line contains four integers X1, Y1, X2, Y2 denoting one additional rule for the painting. (1 <= X1, X2 <= 4, 1 <= Y1, Y2 <= N)

3
1 0
1 3
1 1 2 1
1 1 3 1
4 1 3 1
2 6
1 1 2 1
1 1 3 1
1 1 4 1
1 2 2 2
1 2 3 2
1 2 4 2

Case 1: 67296
Case 2: 00256
Case 3: 32896

//+option:-ansi -Wall -Wextra -pedantic
//+source:http://acm.hdu.edu.cn/showproblem.php?pid=2405
//press <F7> to update the source to mark file.
//press <S-F7> to open the page
#include "iostream"
#include "algorithm"
#include "cstdio"
#include "cstdlib"
#include "cstring"
using namespace std;
#define _ASSERT(a) ({fprintf(stderr,"%s:%d: %s\n", __FILE__, __LINE__, #a); exit(-1);})
#define _FOREACH(a, b) for(__typeof(b.begin())a=b.begin(), a##ed__=b.end(); a!=a##ed__; a++)
#define _FOREACHC(a, b, cond) for (__typeof(b) a=b;(cond); b++, a=b)
#define _QUEUEPROC(cond, U, V) \
for(int u=(U);cond;u=(U))\
_FOREACH(v, V)
#define _STACKPROC(cond, U, V) \
for (int u=(U); cond; u=(U))\
for (bool child=false; !child; child=true)\
_FOREACHC(v, (V), !child)
#define _INCREMENT(over, ...)\
do\
{\
static int over = 0;\
(over)++;\
__VA_ARGS__;\
}while(0)
#define rangedo(i, s, t)\
i=s; i!=t; i++
#define each(a, b)\
__typeof(b.begin())a=b.begin(), a##ed__=b.end(); a!=a##ed__; a++

int T;
int N, M;
int f[16][16][16][16];
int vst[16][16][16][16];
struct Save{
int x1, y1, x2, y2;
}sav[1001];
const int modulo = 100000;
int iter[4];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &N, &M);
memset(vst, 0, sizeof(vst));
for (int i=0; i<M; i++)
scanf("%d%d%d%d", &sav[i].x1, &sav[i].y1, &sav[i].x2, &sav[i].y2);
for (rangedo(iter[0], 0, N+1))
for (rangedo(iter[1], 0, N+1))
for (rangedo(iter[2], 0, N+1))
for (rangedo(iter[3], 0, N+1))
for (int rangedo(i, 0, M))
if ( (iter[sav[i].x1-1] < sav[i].y1)!=
(iter[sav[i].x2-1] < sav[i].y2) )
{
vst[iter[0]][iter[1]][iter[2]][iter[3]]=true;
break;
}
memset(f , 0, sizeof( f));
f[0][0][0][0]=1;
for (int rangedo(color, 1, 257))
{
for (int rangedo(colum, 0, 4))
for (rangedo(iter[0], 0, N+1))
for (rangedo(iter[1], 0, N+1))
for (rangedo(iter[2], 0, N+1))
for (rangedo(iter[3], 0, N+1))
if (iter[colum])
{
int &dp = f[iter[0]][iter[1]][iter[2]][iter[3]];
iter[colum]--;
dp += f[iter[0]][iter[1]][iter[2]][iter[3]];
iter[colum]++;
if (dp>=modulo) dp-=modulo;
}
for (rangedo(iter[0], 0, N+1))
for (rangedo(iter[1], 0, N+1))
for (rangedo(iter[2], 0, N+1))
for (rangedo(iter[3], 0, N+1))
if (vst[iter[0]][iter[1]][iter[2]][iter[3]])
f[iter[0]][iter[1]][iter[2]][iter[3]]=0;
}
_INCREMENT(ncase,
printf("Case %d: %05d\n", ncase, f[N][N][N][N]));
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1