• [B] Board Coloring

  • 时间限制: 10000 ms 内存限制: 32768 K
  • 问题描述
  • 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)
  • 输出
  • For each test cases, you are to output the number of ways of painting. Because there may be too many ways, you are only to output the last five digits. See sample output for further details.
  • 样例输入
  • 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
    
  • 提示
  • 来源
  • HyperHexagon’s Summer Day Gift
  • 操作

显示春菜