#615532 (C++17) No.1397 Analog Graffiti

提出ソース
結果

問題	No.1397 Analog Graffiti
ユーザー	iaNTU
提出日時	2021-02-09 18:27:39
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	1,584 ms / 10,000 ms
コード長	16,369 bytes
コンパイル時間	2,804 ms
コンパイル使用メモリ	222,200 KB
実行使用メモリ	84,956 KB
最終ジャッジ日時	2023-09-21 06:02:03
合計ジャッジ時間	21,565 ms
ジャッジサーバーID （参考情報）	judge13 / judge15
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	25 ms 56,516 KB
testcase_01	AC	28 ms 58,444 KB
testcase_02	AC	1,584 ms 84,832 KB
testcase_03	AC	25 ms 60,256 KB
testcase_04	AC	28 ms 60,428 KB
testcase_05	AC	1,578 ms 84,760 KB
testcase_06	AC	18 ms 58,096 KB
testcase_07	AC	555 ms 84,740 KB
testcase_08	AC	554 ms 84,748 KB
testcase_09	AC	203 ms 58,124 KB
testcase_10	AC	204 ms 58,032 KB
testcase_11	AC	1,534 ms 84,744 KB
testcase_12	AC	310 ms 71,440 KB
testcase_13	AC	1,584 ms 84,684 KB
testcase_14	AC	1,540 ms 84,840 KB
testcase_15	AC	970 ms 84,956 KB
testcase_16	AC	302 ms 71,176 KB
testcase_17	AC	1,508 ms 84,720 KB
testcase_18	AC	1,495 ms 84,724 KB
testcase_19	AC	209 ms 58,100 KB
testcase_20	AC	86 ms 60,256 KB
testcase_21	AC	164 ms 64,544 KB
testcase_22	AC	986 ms 84,764 KB
testcase_23	AC	604 ms 84,716 KB
testcase_24	AC	48 ms 60,256 KB
testcase_25	AC	654 ms 84,676 KB
testcase_26	AC	98 ms 58,160 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 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) 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;

	bitset<10> have, lst_have;
	Connected_State lst_cs = states[lst_connected];

	// check if the state is possible
	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);
	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]) {
			//printf("lst_connected = %d, lst_mask = %d\n", lst_connected, lst_mask);
			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
	assert(false);

Found:

	// count the points
	int points = 0;
	for (int i = 1; i < c; i++) {
		int cnt = 0;
		if (have[i - 1]) cnt++;
		if (have[i]) cnt++;
		if (lst_have[i - 1]) cnt++;
		if (lst_have[i]) cnt++;
		if (cnt & 1) 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, connected);
}

int last_column(int mask, int connected) {
	int ans = 0;

	bitset<10> have;
	Connected_State cs = states[connected];
	vector<int> v;
	
	for (int i = 0; i < c; i++) have[i] = !!(mask & (1 << i));
	for (int i = 0; i < c; i++) if (have[i]) v.PB(i);
	
	int v_sz = int(v.size());
	for (int i = 1; i < v_sz; i++) if (cs[v[i]] != cs[v[0]]) return -1;

	for (int i = 1; i < c; i++) if (have[i] != have[i - 1]) ans++;

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

Mint dp[2][1 << 6][60][880]; // (count) = r, mask, points, state
pair<int, int> trans[1 << 6][1 << 6][880]; // (points, state) = mask, lst_mask, state
int lst_col[1 << 6][880];

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);
	int small_tot = 1 << c;
	
	// !!!
	c += 2;

	tot = 1 << c;


	Pre_Calculate_States();
	
	int states_sz = int(states.size());

	for (int mask = 0; mask < small_tot; mask++) for (int lst_mask = 0; lst_mask < small_tot; lst_mask++) 
		for (int i = 0; i < states_sz; i++) trans[mask][lst_mask][i] = cal(mask << 1, lst_mask << 1, i);

	for (int mask = 1; mask < small_tot; mask++) for (int state = 0; state < states_sz; state++) 
		lst_col[mask][state] = last_column(mask << 1, state);

	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 (int mask = 1; mask < small_tot; mask++) 
			for (int lst_mask = 0; lst_mask < small_tot; lst_mask++) 
				for (int lst_state = 0; lst_state < states_sz; lst_state++) {
					auto [points, state] = trans[mask][lst_mask][lst_state];
					if (points >= 0 && state >= 0) {
						for (int j = points; j <= n; j++)
							dp[i & 1][mask][j][state] += dp[(i ^ 1) & 1][lst_mask][j - points][lst_state];
					}	
		}
		for (int mask = 1; mask < small_tot; mask++) for (int state = 0; state < states_sz; state++)
			if (lst_col[mask][state] >= 0) ans += dp[i & 1][mask][n - lst_col[mask][state]][state] * (r - i + 1);
	}

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

結果

テストケース

ソースコード
