// Exported by Exporter.exe // Included from A.cpp // Compile flags -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2 #include 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 T ABS(T n) {return n >= 0 ? n : -n;} template T gcd(T a, T b) {return b ? gcd(b, a % b) : a;} template 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 static inline int Get_P() { static_assert(is_integral::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 static inline int Get() { static_assert(is_integral::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 static inline void Read_P(T &n) { static_assert(is_integral::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 static inline void Read(T &n) { static_assert(is_integral::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 static inline void Read_Digit(T &n) { static_assert(is_integral::value); char c = Get_Raw_Char(); while (!isdigit(c)) c = Get_Raw_Char(); n = int(c - '0'); return ; } // --- Read multiple --- template static inline void Read(T &n, Targs&... Fargs) { Read(n); return Read(Fargs...); } template static inline void Read_Digit(T &n, Targs&... Fargs) { Read_Digit(n); return Read_Digit(Fargs...); } template static inline void Read_P(T &n, Targs&... Fargs) { Read_P(n); return Read_P(Fargs...); } // --- Read Loop --- template static inline void Read_Loop_i(int i, T *a) {return Read(a[i]);} template static inline void Read_Loop_i(int i, T *a, Targs*... Fargs) { Read(a[i]); return Read_Loop_i(i, Fargs...); } template static inline void Read_Loop(int n, Targs*... Fargs) { for (int i = 1; i <= n; i++) Read_Loop_i(i, Fargs...); return ; } template static inline void Read_Loop_Digit_i(int i, T *a) {return Read_Digit(a[i]);} template 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 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 static inline void Read_Loop_P_i(int i, T *a) {return Read_P(a[i]);} template 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 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 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 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 static inline void Read(T &n, Targs&... Fargs) { Read(n); return Read(Fargs...); } template static inline void Read_P(T &n, Targs&... Fargs) { Read_P(n); return Read_P(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 inline void sort(vector &v) {return sort(v.begin(), v.end());} template inline void sort(int n, T *a) {return sort(a + 1, a + n + 1);} template inline void sort_r(vector &v) {return sort(v.begin(), v.end(), greater());} template inline void sort_r(int n, T *a) {return sort(a + 1, a + n + 1, greater());} // --- Merge --- template inline void Merge_Vec(vector &a, vector &b, vector &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 inline void Discrete(vector &v) { sort(v); v.resize(unique(v.begin(), v.end()) - v.begin()); return ; } // --- Relabel --- template 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 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 struct Mod_Int { constexpr static int Mod() {return kMod;} long long int val; Mod_Int() {val = 0;} template Mod_Int(T x) {val = x;} template Mod_Int(Mod_Int 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; 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 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 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 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 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_popcount(mask & i) + __builtin_popcount(lst_mask & i)) & 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 >> 1, connected); } int last_column(int mask, int connected) { Connected_State cs = states[connected]; int ans = 0, idx = __lg(mask & -mask); for (int i = idx + 1; i < c; i++) if ((mask & (1 << i)) && cs[i] != cs[idx]) return -1; for (int i = 3; i < tot; i <<= 1) if (__builtin_popcount(mask & i) == 1) 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 pair trans[1 << 6][1 << 6][340]; // (points, state) = mask, lst_mask, state int lst_col[1 << 6][340]; 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 = 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