Submission #2945123

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 998244353
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int H, W;

// mask * H + i
int id(int mask, int i)
{
	return mask;
}

pair<int, int> trans(int i, int mask, int nxt)
{
	if (mask & (1 << i)) {
		int ca = -1, cb = -1;

		if (nxt == 1) ca = id(mask ^ (1 << i), (i + 1) % H);
		if (mask & (1 << (i + 1))) cb = id((mask ^ (1 << (i + 1)) ^ (1 << i)) | (nxt << i), (i + 1) % H);

		if (ca == -1 && cb != -1) swap(ca, cb);
		return { ca, cb };
	} else {
		return { id(mask | (nxt << i), (i + 1) % H), -1 };
	}
}

int idl[5];
map<set<int>, int> S[5];
int nxt[5][2000][2];

set<int> reachable_set(set<int> cur, int n, int i)
{
	set<int> reachable;
	for (int mask : cur) {
		auto nxt = trans(i, mask, n);
		if (nxt.first != -1) reachable.insert(nxt.first);
		if (nxt.second != -1) reachable.insert(nxt.second);
	}

	return reachable;
}

int construct(set<int> cur, int i)
{
	if (S[i].count(cur)) return S[i][cur];

	int id = idl[i]++;
	S[i].insert({ cur, id });

//	printf("%d; ", i);
//	for (int mask : cur) printf("%d ", mask);
//	puts("");

	S[i].insert({ cur, 0 });

	for (int n = 0; n < 2; ++n) {
		set<int> reachable = reachable_set(cur, n, i);
		/*
		printf("%d; ", i);
		for (int mask : cur) printf("%d ", mask);
		printf("-> %d; ", (i + 1) % H);
		for (int mask : reachable) printf("%d ", mask);
		puts("");
		*/

		nxt[i][id][n] = construct(reachable, (i + 1) % H);
	}

	return id;
}

int tr[260][32];

const int SIZE = 260;

struct matrix {
	i64 val[SIZE][SIZE];

	matrix() {
		for (int i = 0; i < SIZE; ++i) {
			for (int j = 0; j < SIZE; ++j) {
				val[i][j] = 0;
			}
		}
	}
};

matrix operator*(const matrix& a, const matrix& b)
{
	matrix ret;
	for (int i = 0; i < SIZE; ++i) {
		for (int j = 0; j < SIZE; ++j) {
			i64 tmp = 0;
			for (int k = 0; k < SIZE; ++k) {
				tmp += a.val[i][k] * b.val[k][j];
				if (k % 8 == 7) tmp %= MOD;
			}
			ret.val[i][j] = tmp % MOD;
		}
	}
	return ret;
}

bool isokcheck(int mask)
{
	for (int i = 0; i < H; ++i) {
		if (mask & (1 << i)) {
			if (mask & (1 << (i + 1))) {
				mask ^= (1 << i);
				mask ^= (1 << (i + 1));
			} else return false;
		}
	}
	return true;
}

int main()
{
	scanf("%d%d", &H, &W);

	// powerset construction
	set<int> def;
	def.insert(0);

	for (int i = 0; i < H; ++i) idl[i] = 0;

	construct(def, 0);

	int E = S[0].size();

	for (int i = 0; i < E; ++i) {
		for (int j = 0; j < (1 << H); ++j) {
			int p = i;
			for (int k = 0; k < H; ++k) {
				p = nxt[k][p][(j >> k) & 1];
			}
			tr[i][j] = p;
		}
	}

	matrix M;
	for (int i = 0; i < E; ++i) {
		for (int j = 0; j < (1 << H); ++j) {
			M.val[i][tr[i][j]] += 1;
		}
	}

	matrix sol = M;
	for (int i = 0; i < 30; ++i) {
		if (((W - 1) >> i) & 1) {
			sol = sol * M;
		}
		M = M * M;
	}

	i64 ret = 0;
	for (auto ttt : S[0]) {
		auto s = ttt.first;
		int id = ttt.second;
		bool isok = false;
		for (int v : s) {
			if (isokcheck(v)) isok = true;
		}

		if (isok) ADD(ret, sol.val[0][id]);
	}
	printf("%lld\n", ret);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:132:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &H, &W);
                       ^

Judge Result