列表

详情

NC19042. Pattern

描述

Alice and Bob are playing a game. Alice takes a paper with N ×M points arranging in N rows and M columns. First, Alice colors some points with one of 5 colors: c0,c1,c2,c3,c4. And then, Bob draws some lines between adjacent points which own a common edge. If the color of a point is ci, Bob must draw exactly i lines linking this point. Otherwise, Bob can draw any number of lines linking it. At last, Alice would color the rest points, with the same rules that the point which links i lines should be painted the color ci. After the game, Alice might get different patterns of the colors. Suppose the initial colored paper can lead to totally K patterns, and there are Pi ways for Bob to draw lines for the i-th patterns. Alice wants to know 

输入描述

The first line of input contains an integer t which is the number of test cases. Then t test cases follow. For each test case, the first line consists of two integers N(N ≤ 66), and M(M ≤ 6). The i-th line of the next N lines contains M integers, and among them the j-th integer donates the point (i,j). If the point is panted color ci, the integer is i, otherwise it is −1.

输出描述

For each test cases, output modulo 10007. 

示例1

输入: 

2
2 2
-1 -1
-1 -1
3 3
1 1 1
1 0 1
1 1 1

输出: 

18
4

说明:

In the first case, there would be 15 patterns: 

There is only one way to draw lines which leads to above 14 patterns respectively. 
There are two ways to draw lines which lead to above pattern. Therefore the answer is 18 = 14 + 22.


原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 398ms, 内存消耗: 35292K, 提交时间: 2018-11-22 14:35:34 

#include <cstdio>
#include <cstring>
#include <ctime>

const int MAXN = 10;
const int MAXM = 100;
const int MAXS = 17000;
const int MOD = 10007;

int E2[MAXN * 2];
int T[6][16][20];

void prework()
{
	for (int i = 0; i < MAXN * 2; ++i)
		E2[i] = (1 << i);
	memset(T, 0, sizeof(T));
	for (int i = 0; i < 16; ++i)
	for (int j = 0; j < 16; ++j)
	{
		int k1 = ((i >> 0) & 1) + ((i >> 2) & 1) + ((j >> 0) & 1) + ((j >> 2) & 1);
		int k2 = ((i >> 1) & 1) + ((i >> 3) & 1) + ((j >> 1) & 1) + ((j >> 3) & 1);
		if (k1 == k2)
		{
			T[k1][i][++T[k1][i][0]] = j;
			T[5][i][++T[5][i][0]] = j;
		}
	}
}

int n, m;
int a[MAXM][MAXN];
int f[68][8][16388];

void init()
{
	scanf("%d %d", &m, &n);
	memset(a, 0, sizeof(a));
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j)
		{
			scanf("%d", &a[i][j]);
			if (a[i][j] == -1) a[i][j] = 5;
		}
}

void solve()
{
	int s = E2[(n + 1) << 1];
	memset(f, 0, sizeof(f));
	f[0][0][0] = 1;
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			for (int k = 0; k < s; ++k)
			if (f[i][j][k] != 0)
			{
				int cur = (((k >> j) >> j) & 15);
				for (int ti = 1; ti <= T[a[i][j]][cur][0]; ++ti)
				{
					int next = (k ^ (((cur ^ T[a[i][j]][cur][ti])<<j)<<j));
					f[i][j+1][next] = (f[i][j+1][next] + f[i][j][k]) % MOD;
				}
			}
		}
		for (int k = 0; k < s; ++k)
		if (f[i][n][k] != 0 && (((k >> n) >> n) == 0))
		{
			int next = ((k << 2) & (s - 1));
			f[i+1][0][next] = (f[i+1][0][next] + f[i][n][k]) % MOD;
		}
	}
	printf("%d\n", f[m][0][0]);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	prework();
	int tt;
	scanf("%d", &tt);
	while (tt--)
	{
		init();
		solve();
	}
	fprintf(stderr,"%.2f s\n",clock()*1.0/CLOCKS_PER_SEC);
	return 0;
}

上一题

© 2025 nowcoder.com