結果

問題 No.2907 Business Revealing Dora Tiles
ユーザー 👑 NachiaNachia
提出日時 2024-09-18 23:17:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 82 ms / 3,000 ms
コード長 6,739 bytes
コンパイル時間 8,621 ms
コンパイル使用メモリ 104,648 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 13:25:55
合計ジャッジ時間 17,668 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 6 ms
6,940 KB
testcase_08 AC 20 ms
6,940 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 9 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 4 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 14 ms
6,944 KB
testcase_22 AC 3 ms
6,944 KB
testcase_23 AC 20 ms
6,940 KB
testcase_24 AC 45 ms
6,940 KB
testcase_25 AC 43 ms
6,940 KB
testcase_26 AC 42 ms
6,944 KB
testcase_27 AC 41 ms
6,940 KB
testcase_28 AC 42 ms
6,944 KB
testcase_29 AC 58 ms
6,940 KB
testcase_30 AC 42 ms
6,940 KB
testcase_31 AC 41 ms
6,944 KB
testcase_32 AC 41 ms
6,944 KB
testcase_33 AC 41 ms
6,944 KB
testcase_34 AC 41 ms
6,944 KB
testcase_35 AC 47 ms
6,940 KB
testcase_36 AC 43 ms
6,944 KB
testcase_37 AC 41 ms
6,944 KB
testcase_38 AC 42 ms
6,940 KB
testcase_39 AC 41 ms
6,940 KB
testcase_40 AC 40 ms
6,944 KB
testcase_41 AC 47 ms
6,944 KB
testcase_42 AC 42 ms
6,940 KB
testcase_43 AC 47 ms
6,940 KB
testcase_44 AC 55 ms
6,944 KB
testcase_45 AC 78 ms
6,944 KB
testcase_46 AC 42 ms
6,940 KB
testcase_47 AC 35 ms
6,944 KB
testcase_48 AC 32 ms
6,940 KB
testcase_49 AC 82 ms
6,944 KB
testcase_50 AC 70 ms
6,944 KB
testcase_51 AC 7 ms
6,944 KB
testcase_52 AC 40 ms
6,940 KB
testcase_53 AC 57 ms
6,940 KB
testcase_54 AC 20 ms
6,944 KB
testcase_55 AC 55 ms
6,944 KB
testcase_56 AC 57 ms
6,940 KB
testcase_57 AC 63 ms
6,940 KB
testcase_58 AC 54 ms
6,944 KB
testcase_59 AC 51 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>


namespace nachia{

// reference
// https://drive.google.com/file/d/16g1tfSHUU4NXNTDgaD8FSA1WB4FtJCyV/edit
class NimberManager{
private:
    using u32 = unsigned int;
    using u64 = unsigned long long;
    
    std::vector<u32> precalc1;
    std::vector<u32> inv_precalc1;
    void fill_precalc1(){
        precalc1.assign(1 << 16, 0);
        precalc1[(1 << 8) ^ 1] = 1;
        for(int dd=1; dd<8; dd<<=1){
            int d = 1 << dd;
            int c = d >> 1;
            for(int a0=0; a0<d; a0++) for(int a1=0; a1<d; a1++) if(a0 | a1) {
                for(int b0=0; b0<d; b0++) for(int b1=0; b1<d; b1++) if(b0 | b1) {
                    u64 buf = 0;
                    buf ^= precalc1[(a1 << 8) ^ b1];
                    buf ^= precalc1[(a1 << 8) ^ b0];
                    buf ^= precalc1[(a0 << 8) ^ b1];
                    buf <<= dd;
                    buf ^= precalc1[(c << 8) ^ precalc1[(a1 << 8) ^ b1]];
                    buf ^= precalc1[(a0 << 8) ^ b0];
                    precalc1[(((a1 << dd) ^ a0) << 8) ^ ((b1 << dd) ^ b0)] = buf;
                }
            }
        }
    }

    void inv_precalc() {
        inv_precalc1.resize(256);
        for (int i = 0; i < 256; ++i) {
            for (int j = 0; j < 256; ++j) {
                if (precalc1[(i << 8) ^ j] == 1) {
                    inv_precalc1[i] = j;
                    break;
                }
            }
        }
    }
    
    u64 product_full(u64 a, u64 b, int d = 6) noexcept {
        if(!(a && b)) return 0;
        if(d == 3){ return precalc1[(a << 8) ^ b]; }
        d--;
        u64 lm = ((u64)1 << (1 << d)) - 1;
        u64 us = ((u64)1 << d);
        u64 buf = 0;
        u64 a1b1 = product_full(a >> us, b >> us, d);
        u64 a2b2 = product_full(a & lm, b & lm, d);
        u64 aabb = product_full((a & lm) ^ (a >> us), (b & lm) ^ (b >> us), d);
        buf ^= (aabb ^ a2b2);
        buf <<= us;
        buf ^= a2b2;
        buf ^= product_full((u64)1 << (us - 1), a1b1, d);
        return buf;
    }

    u64 inv_full(u64 a, int d = 6) {
        if (a < 256) {
            return inv_precalc1[a];
        }
        u64 p = 1 << (d - 1);
        u64 a_h = a >> p;
        u64 a_l = a - (a_h << p);
        u64 half_inv = inv_full(product_full(a_h ^ a_l, a_l, d-1) ^ product_full(product_full(a_h, a_h, d-1), 1ULL << (p - 1)), d-1);
        return (product_full(half_inv, a_h, d-1) << p) ^ product_full(half_inv, a_h ^ a_l, d-1);
        return (product_full(half_inv, a_h, d-1) << p) ^ product_full(half_inv, a_h ^ a_l, d-1);
    }

public:
    NimberManager(){ fill_precalc1(); inv_precalc(); }
    
    unsigned long long product(unsigned long long a, unsigned long long b) noexcept { return product_full(a,b); }

    unsigned long long inv(unsigned long long a) noexcept { return inv_full(a); }
};

} // namespace nachia

namespace nachia{

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x8888'8888;
    constexpr u64 mi = 0x1111'1111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}

using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
#include <atcoder/modint>
using Modint = atcoder::static_modint<998244353>;
using namespace std;


void testcase(){
    int N, T; cin >> N >> T;
    vector<vector<u64>> A(T, vector<u64>(N));
    rep(t,T) rep(i,N){ cin >> A[t][i]; A[t][i]--; }
    nachia::NimberManager nim;
    int y = 0;
    for(int x=N-1; x>=0; x--) if(y < T){
        for(int t=y; t<T; t++) if(A[t][x]){
            swap(A[y], A[t]);
            break;
        }
        if(A[y][x] == 0){
            continue;
        }
        auto inv_b = nim.inv(A[y][x]);
        for(int t=0; t<N; t++) A[y][t] = nim.product(A[y][t], inv_b);
        for(int yy=0; yy<T; yy++) if(y != yy){
            auto times = A[yy][x];
            rep(j,N) A[yy][j] ^= nim.product(A[y][j], times);
        }
        y++;
    }
    vector<int> ranks(1 << N);
    auto most_significant = [&](const vector<u64>& x) -> int {
        int f = int(x.size()) - 1;
        while(f >= 0 && x[f] == 0) f--;
        return f;
    };
    auto dfs = [&](auto& dfs, vector<vector<u64>> q, int offseti, int offsetd, int z) -> void {
        if(z == 1){
            ranks[offseti] = offsetd;
            if(q[0][0]) offsetd += 64;
            ranks[offseti + 1] = offsetd;
            return;
        }

        auto q1 = q;
        int d1 = offsetd;
        if(q1.back().back() != 0) d1 += 64;
        q1.pop_back();
        for(auto& qq : q1) qq.pop_back();
        dfs(dfs, move(q1), offseti + (1 << (z-1)), d1, z-1);

        q1 = move(q);
        for(auto& qq : q1) qq.pop_back();
        
        auto q1x = move(q1.back());
        q1.pop_back();
        int b = most_significant(q1x);
        if(b >= 0){
            auto inv_b = nim.inv(q1x[b]);
            for(int t=0; t<=b; t++) q1x[t] = nim.product(q1x[t], inv_b);
            
            for(int t=b+1; t<int(q1.size()); t++){
                auto times = q1[t][b];
                rep(i,b) q1[t][i] ^= nim.product(q1x[i], times);
                q1[t][b] = 0;
            }
            swap(q1[b], q1x);
        }
        
        dfs(dfs, move(q1), offseti, offsetd, z-1);
    };
    vector<vector<u64>> qinit(N, vector<u64>(N));
    rep(i,y) qinit[most_significant(A[i])] = move(A[i]);
    dfs(dfs, qinit, 0, 0, N);
    vector<Modint> W(1<<N);
    rep(i,1<<N) W[i] = Modint(2).pow(64*nachia::Popcount(i)-ranks[i]);
    
    Modint ans = 0;
    rep(i,1<<N) ans += W[i] * ((N - nachia::Popcount(i)) % 2 ? -1 : 1);
    cout << ans.val() << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}
0