結果
| 問題 |
No.2907 Business Revealing Dora Tiles
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2024-07-11 03:00:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,127 bytes |
| コンパイル時間 | 1,649 ms |
| コンパイル使用メモリ | 118,388 KB |
| 最終ジャッジ日時 | 2025-02-22 02:56:38 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 48 TLE * 9 |
ソースコード
#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;
}