結果

問題 No.2907 Business Revealing Dora Tiles
ユーザー 👑 NachiaNachia
提出日時 2024-07-11 03:00:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,127 bytes
コンパイル時間 8,885 ms
コンパイル使用メモリ 119,272 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 12:27:08
合計ジャッジ時間 95,459 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,812 KB
testcase_01 AC 3 ms
6,816 KB
testcase_02 AC 2 ms
6,812 KB
testcase_03 AC 5 ms
6,940 KB
testcase_04 AC 6 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 13 ms
6,940 KB
testcase_07 AC 27 ms
6,944 KB
testcase_08 AC 4 ms
6,944 KB
testcase_09 AC 5 ms
6,940 KB
testcase_10 AC 5 ms
6,940 KB
testcase_11 AC 244 ms
6,944 KB
testcase_12 AC 5 ms
6,940 KB
testcase_13 AC 5 ms
6,940 KB
testcase_14 AC 5 ms
6,944 KB
testcase_15 AC 8 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 5 ms
6,940 KB
testcase_18 AC 62 ms
6,944 KB
testcase_19 AC 7 ms
6,940 KB
testcase_20 AC 4 ms
6,944 KB
testcase_21 AC 474 ms
6,940 KB
testcase_22 AC 57 ms
6,940 KB
testcase_23 AC 1,403 ms
6,940 KB
testcase_24 AC 2,127 ms
6,944 KB
testcase_25 AC 2,120 ms
6,940 KB
testcase_26 AC 2,095 ms
6,940 KB
testcase_27 AC 2,109 ms
6,940 KB
testcase_28 AC 2,105 ms
6,944 KB
testcase_29 AC 2,110 ms
6,940 KB
testcase_30 AC 2,097 ms
6,940 KB
testcase_31 AC 2,083 ms
6,944 KB
testcase_32 AC 2,122 ms
6,944 KB
testcase_33 AC 2,117 ms
6,944 KB
testcase_34 AC 2,126 ms
6,940 KB
testcase_35 AC 2,108 ms
6,944 KB
testcase_36 AC 2,112 ms
6,944 KB
testcase_37 AC 2,128 ms
6,944 KB
testcase_38 AC 2,108 ms
6,944 KB
testcase_39 AC 2,100 ms
6,940 KB
testcase_40 AC 2,080 ms
6,940 KB
testcase_41 AC 2,088 ms
6,940 KB
testcase_42 AC 2,125 ms
6,944 KB
testcase_43 AC 2,109 ms
6,940 KB
testcase_44 AC 2,840 ms
6,940 KB
testcase_45 TLE -
testcase_46 AC 2,641 ms
6,940 KB
testcase_47 AC 1,562 ms
6,940 KB
testcase_48 AC 1,594 ms
6,940 KB
testcase_49 AC 2,849 ms
6,940 KB
testcase_50 AC 2,463 ms
6,940 KB
testcase_51 AC 275 ms
6,940 KB
testcase_52 AC 2,109 ms
6,940 KB
testcase_53 AC 2,675 ms
6,940 KB
testcase_54 AC 1,362 ms
6,940 KB
testcase_55 AC 2,613 ms
6,940 KB
testcase_56 AC 2,622 ms
6,940 KB
testcase_57 AC 2,608 ms
6,944 KB
testcase_58 AC 2,357 ms
6,940 KB
testcase_59 AC 2,635 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <array>
#include <cmath>
#include <atcoder/modint>
#include <bitset>


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;
    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;
                }
            }
        }
    }
    
    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;
    }
public:
    NimberManager(){ fill_precalc1(); }
    
    unsigned long long product(unsigned long long a, unsigned long long b) noexcept { return product_full(a,b); }
};

} // 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++)
#define repr(i,n) for(int i=int(n)-1; i>=0; i--)
const i64 INF = 1001001001001001001;
const char* yn(bool x){ return x ? "Yes" : "No"; }
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; }
template<typename A> using nega_queue = std::priority_queue<A,std::vector<A>,std::greater<A>>;
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;
    vector<vector<u64>> F(T*64, vector<u64>(N));
    rep(t,T) rep(i,N) rep(b,64){
        u64 x = nim.product(A[t][i], u64(1) << b);
        rep(e,64) F[t*64+e][i] |= ((x >> e) & 1) << b;
    }
    int y = 0;
    repr(x,N*64) if(y < T*64){
        for(int t=y; t<T*64; t++) if(F[t][x/64] & (u64(1)<<(x%64))){
            swap(F[y], F[t]);
            break;
        }
        if(!(F[y][x/64] & (u64(1)<<(x%64)))){
            continue;
        }
        for(int yy=0; yy<T*64; yy++) if(y != yy) if(F[yy][x/64] & (u64(1)<<(x%64))){
            rep(j,N) F[yy][j] ^= F[y][j];
        }
        y++;
    }
    vector<int> ranks(1 << N);
    auto msb = [&](const vector<u64>& x) -> int {
        int f = int(x.size()) - 1;
        while(f >= 0 && x[f] == 0) f--;
        if(f < 0) return -1;
        return f * 64 + nachia::LsbIndex(x[f]);
    };
    auto dfs = [&](auto& dfs, vector<vector<u64>> q, int offseti, int offsetd, int z) -> void {
        if(z == 1){
            ranks[offseti] = offsetd;
            for(auto& qq : q) if(qq[0]) offsetd++;
            ranks[offseti + 1] = offsetd;
            return;
        }
        auto q1 = q;
        int d1 = offsetd;
        rep(t,64){
            if(q1.back().back() != 0) d1++;
            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();
        rep(t,64){
            auto q1x = move(q1.back());
            q1.pop_back();
            int b = msb(q1x);
            if(b >= 0){
                for(int t=b+1; t<int(q1.size()); t++){
                    if((q1[t][b/64] >> (b%64)) & 1){
                        rep(i,q1x.size()) q1[t][i] ^= q1x[i];
                    }
                }
                swap(q1[b], q1x);
            }
        }
        dfs(dfs, move(q1), offseti, offsetd, z-1);
    };
    vector<vector<u64>> qinit(N*64, vector<u64>(N));
    rep(i,y) qinit[msb(F[i])] = move(F[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