結果

問題 No.1397 Analog Graffiti
ユーザー iaNTU
提出日時 2021-02-10 17:39:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 394 ms / 10,000 ms
コード長 16,967 bytes
コンパイル時間 3,834 ms
コンパイル使用メモリ 214,952 KB
最終ジャッジ日時 2025-01-18 17:05:27
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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_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<int, int> 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0