結果

問題 No.1397 Analog Graffiti
ユーザー iaNTUiaNTU
提出日時 2021-02-10 18:00:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 209 ms / 10,000 ms
コード長 16,923 bytes
コンパイル時間 2,428 ms
コンパイル使用メモリ 233,988 KB
実行使用メモリ 14,148 KB
最終ジャッジ日時 2024-07-08 04:28:59
合計ジャッジ時間 5,796 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
13,824 KB
testcase_01 AC 5 ms
13,876 KB
testcase_02 AC 167 ms
14,020 KB
testcase_03 AC 5 ms
13,824 KB
testcase_04 AC 5 ms
13,696 KB
testcase_05 AC 209 ms
13,952 KB
testcase_06 AC 10 ms
13,824 KB
testcase_07 AC 172 ms
13,952 KB
testcase_08 AC 146 ms
14,020 KB
testcase_09 AC 15 ms
13,696 KB
testcase_10 AC 15 ms
13,696 KB
testcase_11 AC 169 ms
14,016 KB
testcase_12 AC 27 ms
13,824 KB
testcase_13 AC 167 ms
14,148 KB
testcase_14 AC 174 ms
14,144 KB
testcase_15 AC 160 ms
14,080 KB
testcase_16 AC 27 ms
13,824 KB
testcase_17 AC 168 ms
14,020 KB
testcase_18 AC 166 ms
14,024 KB
testcase_19 AC 15 ms
13,944 KB
testcase_20 AC 8 ms
13,824 KB
testcase_21 AC 13 ms
13,824 KB
testcase_22 AC 155 ms
14,144 KB
testcase_23 AC 146 ms
14,020 KB
testcase_24 AC 6 ms
13,824 KB
testcase_25 AC 147 ms
14,016 KB
testcase_26 AC 8 ms
13,696 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Exported by Exporter.exe

// Included from A.cpp
// Compile flags -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define MTP make_tuple
#define R Read
#define RD Read_Digit
#define RP Read_P
#define RL Read_Loop
#define RLD Read_Loop_Digit
#define RLP Read_Loop_P
typedef long long int ll;
typedef unsigned long long int ull;

constexpr int kN = int(1E5 + 10);
constexpr int kMod = 998244353;
constexpr int kInf = 0x3f3f3f3f;
// constexpr ll kInf = 0x3f3f3f3f3f3f3f3f;
// constexpr double kPi = acos(-1);
// constexpr double kEps = 1E-9;

template <typename T> T ABS(T n) {return n >= 0 ? n : -n;}
template <typename T> T gcd(T a, T b) {return b ? gcd(b, a % b) : a;}
template <typename T> T mex(T a, T b) {return (a == 0 || b == 0) ? ((a == 1 || b == 1) ? 2 : 1) : 0;}


// Included from C:\Users\ianli\Desktop\CP\template\Various\Fast_IO\Fast_IO.cpp
// --- Get ---
static inline char Get_Raw_Char() {
	static char buf[1 << 16], *p = buf, *end = buf;
	if (p == end) {
		if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';
		p = buf;
	}
	return *p++;
}

static inline int Get_Digit() {
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	return int(c - '0');
}

template <typename T> static inline int Get_P() {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	T ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	return ret;
}

template <typename T> static inline int Get() {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	bool neg = false;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	T ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	if (neg) return -ret;
	return ret;
}

// --- Read ---
template <typename T> static inline void Read_P(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	return ;
}

template <typename T> static inline void Read(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	bool neg = false;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	if (neg) n = -n;
	return ;
}

template <typename T> static inline void Read_Digit(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	n = int(c - '0');
	return ;
}

// --- Read multiple ---
template <typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {
	Read(n);
	return Read(Fargs...);
}

template <typename T, typename... Targs> static inline void Read_Digit(T &n, Targs&... Fargs) {
	Read_Digit(n);
	return Read_Digit(Fargs...);
}

template <typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {
	Read_P(n);
	return Read_P(Fargs...);
}

// --- Read Loop ---
template <typename T> static inline void Read_Loop_i(int i, T *a) {return Read(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_i(int i, T *a, Targs*... Fargs) {
	Read(a[i]);
	return Read_Loop_i(i, Fargs...);
}
template <typename... Targs> static inline void Read_Loop(int n, Targs*... Fargs) {
	for (int i = 1; i <= n; i++) Read_Loop_i(i, Fargs...);
	return ;
}

template <typename T> static inline void Read_Loop_Digit_i(int i, T *a) {return Read_Digit(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_Digit_i(int i, T *a, Targs*... Fargs) {
	Read_Digit(a[i]);
	return Read_Loop_Digit_i(i, Fargs...);
}
template <typename... Targs> static inline void Read_Loop_Digit(int n, Targs*... Fargs) {
	for (int i = 1; i <= n; i++) Read_Loop_Digit_i(i, Fargs...);
	return ;
}

template <typename T> static inline void Read_Loop_P_i(int i, T *a) {return Read_P(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_P_i(int i, T *a, Targs*... Fargs) {
	Read_P(a[i]);
	return Read_Loop_P_i(i, Fargs...);
}
template <typename... Targs> static inline void Read_Loop_P(int n, Targs*... Fargs) {
	for (int i = 1; i <= n; i++) Read_Loop_P_i(i, Fargs...);
	return ;
}

// --- Float ---

template <int mul, typename T> static inline void Read(T &n) {
	char c = Get_Raw_Char();
	bool neg = false;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	
	int cnt = 0;

	if (c == '.') {
		while (isdigit(c = Get_Raw_Char())) {
			n = n * 10 + int(c - '0');
			cnt++;
		}
	}

	while (cnt < mul) {
		n = n * 10;
		cnt++;
	}

	if (neg) n = -n;
	return ;
}

template <int mul, typename T> static inline void Read_P(T &n) {
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	
	int cnt = 0;

	if (c == '.') {
		while (isdigit(c = Get_Raw_Char())) {
			n = n * 10 + int(c - '0');
			cnt++;
		}
	}

	while (cnt < mul) {
		n = n * 10;
		cnt++;
	}
	return ;
}

template <int mul, typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {
	Read<mul>(n);
	return Read<mul>(Fargs...);
}

template <int mul, typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {
	Read_P<mul>(n);
	return Read_P<mul>(Fargs...);
}

// --- Output __int128 ---
/*
void Print128(__int128 x) {
	if (x < 0) {
		printf("-");
		x = -x;
	}
	if (x == 0) printf("0");
	else {
		static int val[100];
		int idx = -1;
		while (x) {
			val[++idx] = x % 10;
			x /= 10;
		}
		while (idx >= 0) printf("%d", val[idx--]);
	}
} 
*/
// End of C:\Users\ianli\Desktop\CP\template\Various\Fast_IO\Fast_IO.cpp


// Included from C:\Users\ianli\Desktop\CP\template\Various\Useful_Functions\Useful_Functions.cpp
// --- sort ---
template <typename T> inline void sort(vector<T> &v) {return sort(v.begin(), v.end());}
template <typename T> inline void sort(int n, T *a) {return sort(a + 1, a + n + 1);}
template <typename T> inline void sort_r(vector<T> &v) {return sort(v.begin(), v.end(), greater<T>());}
template <typename T> inline void sort_r(int n, T *a) {return sort(a + 1, a + n + 1, greater<T>());}

// --- Merge ---
template <typename T> inline void Merge_Vec(vector<T> &a, vector<T> &b, vector<T> &c) {
	if (c.size() < a.size() + b.size()) c.resize(a.size() + b.size());
	merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
	return ;
}

// --- Discrete ---
template <typename T> inline void Discrete(vector<T> &v) {
	sort(v);
	v.resize(unique(v.begin(), v.end()) - v.begin());
	return ;
}

// --- Relabel ---
template <typename T> inline void relabel(int n, T *val, T *dist) {
	if (!dist) dist = val;
	T *tmp = new T[n + 1];
	memcpy(tmp, val, sizeof(T) * (n + 1));
	sort(n, tmp);
	int sz = unique(tmp + 1, tmp + n + 1) - (tmp + 1);
	for (int i = 1; i <= n; i++) dist[i] = lower_bound(tmp + 1, tmp + sz + 1, val[i]) - tmp;
	delete tmp;
	return ;
}
// End of C:\Users\ianli\Desktop\CP\template\Various\Useful_Functions\Useful_Functions.cpp


// Included from C:\Users\ianli\Desktop\CP\template\Math\Mod_Int\Mod_Int.cpp
template <typename T> T Pow(T a, long long int b) {
	T ans(1);
	while (b) {
		if (b & 1) ans *= a;
		a *= a;
		b >>= 1;
	}
	return ans;
}

template <int kMod> struct Mod_Int {
	constexpr static int Mod() {return kMod;}

	long long int val;
	Mod_Int() {val = 0;}
	template <typename T> Mod_Int(T x) {val = x;}
	template <int nMod> Mod_Int(Mod_Int<nMod> x) {val = x.val % kMod;}

	Mod_Int inv() const {return Pow(*this, kMod - 2);} 

	Mod_Int operator + (const Mod_Int &x) const {
		Mod_Int ans(val + x.val);
		if (ans.val >= kMod) ans.val -= kMod;
		return ans;
	}
	Mod_Int operator - (const Mod_Int &x) const {
		Mod_Int ans(val - x.val);
		if (ans.val < 0) ans.val += kMod;
		return ans;
	}
	Mod_Int operator * (const Mod_Int &x) const {return Mod_Int(val * x.val % kMod);}
	Mod_Int operator / (const Mod_Int &x) const {return *this * x.inv();}
	Mod_Int operator ^ (const Mod_Int &x) const {return Pow(*this, x.val);}
	Mod_Int operator << (const int &x) const {return (val << x) % kMod;}

	Mod_Int operator += (const Mod_Int &x) {
		val += x.val;
		if (val >= kMod) val -= kMod;
		return *this;
	}
	Mod_Int operator -= (const Mod_Int &x) {
		val -= x.val;
		if (val < 0) val += kMod;
		return *this;
	}
	Mod_Int operator *= (const Mod_Int &x) {
		val = val * x.val % kMod;
		return *this;
	}
	Mod_Int operator /= (const Mod_Int &x) {
		val = val * x.inv().val % kMod;
		return *this;
	}
	Mod_Int operator ^= (const Mod_Int &x) {
		val = Pow(*this, x.val).val;
		return *this;
	}
	Mod_Int operator <<= (const int &x) {
		val = (val << x) % kMod;
		return *this;
	}

	Mod_Int operator ++(int) {
		val++;
		if (val >= kMod) val -= kMod;
		return *this;
	}
	Mod_Int operator --(int) {
		val--;
		if (val < 0) val += kMod;
		return *this;
	}

	bool operator == (const Mod_Int &x) const {return val == x.val;}
	bool operator != (const Mod_Int &x) const {return val != x.val;}
};

using Mint = Mod_Int<kMod>;

namespace Factorial {
	Mint *f, *inf;
	void Pre_Factorial(const int &sz) {
		f = new Mint[sz + 1];
		inf = new Mint[sz + 1];
		f[0] = f[1] = inf[0] = inf[1] = 1;
		for (int i = 2; i <= sz; i++) f[i] = f[i - 1] * i;
		inf[sz] = f[sz].inv();
		for (int i = sz; i > 2; i--) inf[i - 1] = inf[i] * i;
		return ;
	}
	inline Mint P(const int &n, const int &m) {return f[n] * inf[m];}
	inline Mint C(const int &n, const int &m) {return f[n] * inf[m] * inf[n - m];}
	inline Mint H(const int &n, const int &m) {return f[n + m - 1] * inf[m] * inf[n - 1];}
	inline Mint C(const int &n) {return f[n << 1] * inf[n] * inf[n + 1];}
}

namespace Factorial_No_Inf {
	Mint *f;
	void Pre_Factorial(const int &sz) {
		f = new Mint[sz + 1];
		f[0] = f[1] = 1;
		for (int i = 2; i <= sz; i++) f[i] = f[i - 1] * i;
		return ;
	}
	inline Mint P(const int &n, const int &m) {return f[n] / f[m];}
	inline Mint C(const int &n, const int &m) {return f[n] / (f[m] * f[n - m]);}
	inline Mint H(const int &n, const int &m) {return f[n + m - 1] / (f[m] * f[n - 1]);}
	inline Mint C(const int &n) {return f[n << 1] / (f[n] * f[n + 1]);}
}
// End of C:\Users\ianli\Desktop\CP\template\Math\Mod_Int\Mod_Int.cpp


int c, tot;

struct Connected_State {
	vector<int> v;
	void pull() {
		static int idx[8];
		memset(idx, 0x3f, sizeof(idx));
		for (int i = 0; i < c; i++) if (idx[v[i]] == kInf) idx[v[i]] = i;
		for (int i = 0; i < 8; i++) for (int j = i + 1; j < 8; j++) if (idx[i] > idx[j]) {
			swap(idx[i], idx[j]);
			for (int k = 0; k < c; k++) if (v[k] == i || v[k] == j) v[k] ^= i ^ j;
		}
		return ;
	}

	bool operator == (const Connected_State &x) const {
		for (int i = 0; i < c; i++) if (v[i] != x.v[i]) return false;
		return true;
	}

	int& operator [] (int x) {return v[x];}
};

vector<Connected_State> states;
void Pre_Calculate_States() {
	Connected_State cs;
	cs.v.resize(c);
	
	auto Dfs = [&](auto self, int cur, int cur_mx) -> void {
		//printf("Dfs(%d, %d)\n", cur, cur_mx);
		//printf("cur :"); for (int i = 0; i < c; i++) printf(" %d", cs[i]); printf("\n");
		if (cur == c - 1) {
			static int color[8];

			memset(color, -1, sizeof(color));

			color[0] = 0;
			for (int j = 1; j < c; j++) 
				if (cs[j] != cs[j - 1]) color[j] = color[j - 1] ^ 1;
				else color[j] = color[j - 1];

			for (int i = 0; i < c; i++) for (int j = i + 1; j < c; j++) 
				if (cs[i] == cs[j] && color[i] != color[j]) return ;

			states.PB(cs);
		}
		else {
			for (int i = 0; i <= cur_mx; i++) {
				cs[cur] = i;
				self(self, cur + 1, cur_mx);
			}
			self(self, cur + 1, cs[cur] = cur_mx + 1);
		}
		return ;
	};
	Dfs(Dfs, 1, 0);

	//int sz = int(states.size());
	//printf("size = %d\n", sz);
	//for (int i = 0; i < sz; i++) {
	//	printf("i = %d:", i); for (int j = 0; j < c; j++) printf(" %d", states[i][j]); printf("\n");
	//}
	//printf("done\n");

	return ;
}

pair<int, int> cal(int mask, int lst_mask, int lst_connected) { // return (points, connected)
	// count the connected

	static int p[20];
	static auto _Find = [&](auto self, int n) -> int {return p[n] == n ? n : p[n] = self(self, p[n]);};
	static auto Find = [&](int n) -> int {return _Find(_Find, n);};
	static auto Merge = [&](int l, int r) -> void {
		p[Find(r)] = Find(l);
		return ;
	};
	for (int i = 0; i < (c << 1); i++) p[i] = i;

	Connected_State lst_cs = states[lst_connected];

	bitset<10> have, lst_have;

	for (int i = 0; i < c; i++) have[i] = !!(mask & (1 << i));
	for (int i = 0; i < c; i++) lst_have[i] = !!(lst_mask & (1 << i));

	for (int i = 1; i < c; i++) if (lst_have[i] == lst_have[i - 1]) Merge(i + c, i + c - 1);

	// check if the state is possible
	for (int i = 0; i < c; i++) for (int j = i + 1; j < c; j++) 
		if (Find(i + c) == Find(j + c) && lst_cs[i] != lst_cs[j]) return MP(-1, -1);

	for (int i = 1; i < c; i++) 
		if (lst_have[i] != lst_have[i - 1] && lst_cs[i] == lst_cs[i - 1]) return MP(-1, -1);

	for (int i = 1; i < c; i++) if (have[i] == have[i - 1]) Merge(i - 1, i);
	for (int i = 0; i < c; i++) if (have[i] == lst_have[i]) Merge(i, i + c);

	for (int i = 0; i < c; i++) for (int j = i + 1; j < c; j++) if (lst_cs[i] == lst_cs[j]) Merge(i + c, j + c);

	// check if valid
	bitset<20> alive;
	alive.reset();
	for (int i = 0; i < c; i++) alive[Find(i)] = true;

	for (int i = 0; i < c; i++) if (!alive[Find(i + c)]) return MP(-1, -1);

	Connected_State cs;
	cs.v.resize(c);
	vector<int> vals;
	for (int i = 0; i < c; i++) vals.PB(Find(i));
	sort(vals);
	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
	for (int i = 0; i < c; i++) cs[i] = lower_bound(vals.begin(), vals.end(), Find(i)) - vals.begin();
	cs.pull();

	int connected;
	static int cs_size = int(states.size());
	for (int i = 0; i < cs_size; i++) if (cs == states[i]) {
		connected = i;
		goto Found;
	}
	// not found
	
	printf("have :"); for (int i = 0; i < c; i++) printf("%d", have[i] ? 1 : 0); printf("\n");
	printf("lst_have :"); for (int i = 0; i < c; i++) printf("%d", lst_have[i] ? 1 : 0); printf("\n");
	printf("cs :"); for (int i = 0; i < c; i++) printf("%d", cs[i]); printf("\n");
	printf("lst_cs :"); for (int i = 0; i < c; i++) printf("%d", lst_cs[i]); printf("\n");

	assert(false);

Found:

	// count the points
	int points = 0;
	for (int i = 3; i < tot; i <<= 1) if (__builtin_parity((mask ^ lst_mask) & i)) points++;
	
	// points should be an even number
	//if (points & 1) {
	//	printf("have :"); for (int i = 0; i < c; i++) printf("%d", have[i] ? 1 : 0); printf("\n");
	//	printf("lst_have :"); for (int i = 0; i < c; i++) printf("%d", lst_have[i] ? 1 : 0); printf("\n");
	//	printf("points = %d\n", points);
	//	
	//}
	//assert(!(points & 1));

	return MP(points >> 1, connected);
}

int last_column(int mask, int connected) {
	Connected_State cs = states[connected];
	int ans = 0, idx = __lg(mask & -mask);

	for (int i = 0; i < c - 1; i++) if (!(mask & (3 << i)) && cs[i] != cs[i + 1]) return -1;
	for (int i = idx + 1; i < c; i++) if ((mask & (1 << i)) && cs[i] != cs[idx]) return -1;
	for (int i = 0; i < c - 1; i++) if (__builtin_parity(mask & (3 << i))) ans++;

	// ans should be an even number
	//assert(!(ans & 1));
	return ans >> 1;
}

Mint dp[2][1 << 6][30][340]; // (count) = r, mask, points, state
vector<tuple<int, int, int, int, int>> trans; // (mask, lst_mask, lst_state, points, state) = mask, lst_mask
vector<tuple<int, int, int>> lst_col; // (state, points) = mask

int main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//freopen("file_name", "r", stdin);
	//freopen("file_name", "w", stdout);
	int r, n; RP(r, c, n);
	n >>= 1;
	int small_tot = 1 << c;
	
	// !!!
	c += 2;

	tot = 1 << c;

	Pre_Calculate_States();
	//return 0;
	
	int states_sz = int(states.size());

	for (int mask = 1; mask < small_tot; mask++) for (int lst_mask = 0; lst_mask < small_tot; lst_mask++) 
		for (int i = 0; i < states_sz; i++) {
			pair<int, int> tmp = cal(mask << 1, lst_mask << 1, i);
			if (tmp.F >= 0 && tmp.F <= n) trans.PB(MTP(mask, lst_mask, i, tmp.F, tmp.S));
		}

	for (int mask = 1; mask < small_tot; mask++) for (int state = 0; state < states_sz; state++) {
		int tmp = last_column(mask << 1, state);
		if (tmp >= 0 && tmp <= n) lst_col.PB(MTP(mask, state, tmp));
	}

	dp[0][0][0][0] = 1;

	Mint ans = 0;

	for (int i = 1; i <= r; i++) {
		memset(dp[i & 1], 0, sizeof(dp[i & 1]));
		for (auto [mask, lst_mask, lst_state, points, state] : trans) 
			for (int j = points; j <= n; j++) 
				dp[i & 1][mask][j][state] += dp[(i ^ 1) & 1][lst_mask][j - points][lst_state];

		Mint tmp;
		for (auto [mask, state, points] : lst_col) tmp += dp[i & 1][mask][n - points][state];

		ans += tmp * (r - i + 1);
	}

	printf("%lld\n", ans.val);
}
// End of A.cpp
0