C++(clang++ 11.0.1) 解法, 执行用时: 21ms, 内存消耗: 1352K, 提交时间: 2022-12-11 15:10:13

#include<bits/stdc++.h>
using namespace std;
#define MAXN	30
#define TMPN	15
#define HASH	1000005
#define P	100003
#define Q	10000000000000000
struct Extended_LL {long long a, b; };
Extended_LL operator + (Extended_LL x, Extended_LL y) {
	Extended_LL c = {x.a + y.a, x.b + y.b};
	c.a += c.b / Q; c.b %= Q;
	return c;
}
struct Hash_Table {
	int head[P], nxt[HASH];
	int curr[HASH], size;
	Extended_LL value[HASH];
	void clear() {
		size = 0;
		memset(head, 0, sizeof(head));
	}
	void modify(int x, Extended_LL val) {
		int pos = x % P;
		for (int i = head[pos]; i; i = nxt[i])
			if (curr[i] == x) {
				value[i] = value[i] + val;
				return;
			}
		size++;
		curr[size] = x;
		value[size] = val;
		nxt[size] = head[pos];
		head[pos] = size;
	}
};
Hash_Table ans[2];
int n, m, ex, ey, num[MAXN], bit[MAXN], all;
Extended_LL finalans;
void Extend(int x, int y, int curr, int dest, Extended_LL val) {
	int tmpy = num[y] & curr;
	int tmpx = num[y - 1] & curr;
	int typey = 0, typex = 0;
	if (tmpy) {
		if (tmpy & (1 << 2 * y)) typey = 1;
		else typey = 2;
	}
	if (tmpx) {
		if (tmpx & (1 << 2 * (y - 1))) typex = 1;
		else typex = 2; 
	}
	if (x == ex && y == ey) {
		int tcurr = curr ^ tmpy ^ tmpx;
		if (tcurr == 0 && typex == 1 && typey == 2) finalans = finalans + val;
		return;
	}
	if (tmpy == 0 && tmpx == 0) {
		if (y == m) return;
		else {
			ans[dest].modify(curr | (1 << 2 * (y - 1)) | (2 << 2 * y), val);
			return;
		}
	}
	if (tmpy != 0 && tmpx != 0) {
		int tcurr = curr ^ tmpx ^ tmpy;
		if (typex == 1 && typey == 2) return;
		if (typex == 2 && typey == 1) {
			if (y != m) {
				ans[dest].modify(tcurr, val);
				return;
			} else {
				ans[dest].modify(tcurr << 2, val);
				return;
			}
		}
		static int type[MAXN], q[MAXN], tnp[MAXN], pir[MAXN];
		int top = 0;
		for (int i = 0; i <= m; i++) {
			tnp[i] = curr & num[i];
			type[i] = 0;
			if (tnp[i]) {
				if (tnp[i] & (1 << 2 * i)) type[i] = 1;
				else type[i] = 2;
			}
		}
		for (int i = 0; i <= m; i++) {
			if (type[i] == 1) q[++top] = i;
			if (type[i] == 2) {
				pir[q[top]] = i;
				pir[i] = q[top];
				top--;
			}
		}
		if (typex == 1 && typey == 1) {
			ans[dest].modify(tcurr ^ tnp[pir[y]] ^ (1 << 2 * pir[y]), val);
			return;
		} else {
			if (y != m) {
				ans[dest].modify(tcurr ^ tnp[pir[y - 1]] ^ (2 << 2 * pir[y - 1]), val);
				return;
			} else {
				ans[dest].modify((tcurr ^ tnp[pir[y - 1]] ^ (2 << 2 * pir[y - 1])) << 2, val);
				return;
			}
		}
	}
	if (tmpy == 0) {
		int tcurr = curr ^ tmpx;
		if (y != m) ans[dest].modify(curr, val);
		else ans[dest].modify(curr << 2, val);
		if (y != m) ans[dest].modify(tcurr | (typex << 2 * y), val);
	} else {
		int tcurr = curr ^ tmpy;
		if (y != m) ans[dest].modify(curr, val);
		if (y != m) ans[dest].modify(tcurr | (typey << 2 * (y - 1)), val);
		else ans[dest].modify((tcurr | (typey << 2 * (y - 1))) << 2, val);
	}
}
void work(int x, int y, int now) {
	int tx = x, ty = y + 1;
	if (ty > m) ty = 1, tx++;
	ans[now ^ 1].clear();
	for (int i = 1; i <= ans[now].size; i++)
		Extend(x, y, ans[now].curr[i], now ^ 1, ans[now].value[i]);
	if (x == ex && y == ey) return;
	else work(tx, ty, now ^ 1);
}
void print(Extended_LL x) {
	if (x.a) {
		printf("%lld", x.a);
		long long now = Q / 10;
		while (now) {
			printf("%lld", x.b / now);
			x.b %= now;
			now /= 10;
		}
		printf("\n");
	} else printf("%lld\n", x.b);
}
int main() {
	scanf("%d%d", &m, &n);
	if (n == 1 || m == 1) {
		printf("1\n");
		return 0;
	}
	num[0] = 3; bit[0] = 1;
	for (int i = 1; i <= m + 1; i++)
		num[i] = num[i - 1] << 2;
	for (int i = 1; i < MAXN; i++)
		bit[i] = bit[i - 1] << 1;
	ex = n, ey = m;
	if (ex == 0) printf("0\n");
	else {
		ans[0].clear();
		ans[1].clear(); 
		ans[0].modify(0, (Extended_LL) {0, 1});
		finalans = (Extended_LL) {0, 0};
		work(1, 1, 0);
		finalans = finalans + finalans;
		print(finalans);
	}
	return 0;
}