比赛-thh学长的训练赛2 (20 Aug, 2018)

A. graph##

设第 (i) 个图 (C) 逆时针旋转 (90°) 得到 (A) ，顺时针旋转 (90°) 得到 (B) ，则第 (i + 1) 个图是：
A B
C C
这样就可以把第 (i) 张图划分成四个部分。考虑把某个第 (i) 个图的坐标代换成第 (i - 1) 张图中的坐标，写一个递归即可。
假设输出矩形的长、宽分别为 (x,y) ，时间复杂度 (O(n cdot xy)) 。

#include <cstdio>

int P[35];
bool MA[4][4];

bool fun(int n, int x, int y)
{
	if (n == 1)
		return MA[x][y];
	if (x > P[n - 1] && y <= P[n - 1])
		return fun(n - 1, x - P[n - 1], y);
	if (x > P[n - 1] && y > P[n - 1])
		return fun(n - 1, x - P[n - 1], y - P[n - 1]);
	if (x <= P[n - 1] && y <= P[n - 1])
		return fun(n - 1, y, P[n - 1] - x + 1);
	if (x <= P[n - 1] && y > P[n - 1])
		return fun(n - 1, P[n] - y + 1, x);
	return 0;
}

int main()
{
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	
	int N, A, B, C, D;
	scanf("%d%d%d%d%d", &N, &A, &B, &C, &D);
	P[0] = 1;
	for (int i = 1; i <= N; ++i)
		P[i] = P[i - 1] << 1;
	MA[1][2] = 1;
	for (int i = A; i <= C; ++i) {
		for (int j = B; j <= D; ++j)
			printf("%d", fun(N, i, j));
		printf("
");
	}
	return 0;
}

B. calc##

(f(i, j, k, s)) 表示 (i) 点在总共还有 (j) 条边可以连的情况下，考虑连到编号更小的 (k) 点，并且 (i-L+1,i-L+2,...,i) 这 (L) 个点对应的奇偶性，用二进制状态表示为 (s) 。
然后讨论：

• (i) 直接向 (k) 连边
• (i) 连到 (k-1) （要求 (i) 和 (k-1) 满足 (L) 的限制，即差的绝对值不超过 (L) ）
• (i) 停止连边，用 (i-1) 号点去连边（要求 (i) 度数为偶数，满足无向图欧拉回路的条件）

#include <stdio.h>
#include <string.h>

using namespace std;

const int MOD = 998244353;

int f[31][31][31][1 << 8], N, M, L;

inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }

int dfs(int i, int j, int k, int s)
{
	if (f[i][j][k][s] != -1) return f[i][j][k][s];
	if (j == 0)
		return f[i][j][k][s] = s == 0;
	if (i == 1) return f[i][j][k][s] = 0;
	int tmp = dfs(i, j - 1, k, s ^ 1 ^ (1 << (i - k)));
	if (k - 1 >= 1 && i - (k - 1) <= L)
		tmp = add(tmp, dfs(i, j, k - 1, s));
	else if (s & 1 ^ 1)
		tmp = add(tmp, dfs(i - 1, j, i - 2, s >> 1));
	return f[i][j][k][s] = tmp;
}

int main()
{
	scanf("%d%d%d", &N, &M, &L);
	memset(f, -1, sizeof f);
	printf("%d
", dfs(N, M, N - 1, 0));
	return 0;
}