結果

問題 No.2907 Business Revealing Dora Tiles
コンテスト
ユーザー amentorimaru
提出日時 2024-09-17 00:31:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 202 ms / 3,000 ms
コード長 3,831 bytes
コンパイル時間 12,360 ms
コンパイル使用メモリ 188,572 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 13:06:19
合計ジャッジ時間 21,684 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <atcoder/all>

using namespace std;
using u64 = unsigned long long;
using mint = atcoder::modint998244353;

u64 pre_prod[256][256] = { 0 };
u64 pre_inv[256] = { 0 };

u64 nim_product(u64 a, u64 b, int d = 6) noexcept {
  if (min(a, b) <= 1) return a * b;
  if (a < 256 && b < 256 && pre_prod[a][b]) { return pre_prod[a][b]; }

  d--;
  u64 d_pow = 1ULL << d;
  u64 d_pow_pow = 1ULL << d_pow;
  if (a < d_pow_pow && b < d_pow_pow) {
    return nim_product(a, b, d);
  }

  u64 au = a >> d_pow;
  u64 al = a - (au << d_pow);
  u64 bu = b >> d_pow;
  u64 bl = b - (bu << d_pow);
  u64 aubu = nim_product(au, bu, d);
  u64 albu = nim_product(al, bu, d);
  u64 aubl = nim_product(au, bl, d);
  u64 albl = nim_product(al, bl, d);

  u64 res = ((aubu ^ aubl ^ albu) << d_pow) ^ (nim_product(aubu, d_pow_pow / 2, d)) ^ (albl);

  if (a < 256 && b < 256)
    pre_prod[a][b] = pre_prod[b][a] = res;
  return res;
}

u64 nim_product_inv(u64 a, int d = 6) {
  if (a < 256)
    return pre_inv[a];
  d--;
  u64 d_pow = 1 << d;
  u64 au = a >> d_pow;
  u64 al = a - (au << d_pow);
  u64 half_inv = nim_product_inv(nim_product(au ^ al, al, d) ^ nim_product(nim_product(au, au, d), 1ULL << (d_pow - 1)), d);
  return (nim_product(half_inv, au, d) << d_pow) ^ nim_product(half_inv, au ^ al, d);
}


int main() {
  // precalc
  for (int a = 1; a < 256; a++) {
    for (int b = a; b < 256; b++) {
      u64 c = nim_product(a, b);
      if (c == 1) {
        pre_inv[a] = b;
        pre_inv[b] = a;
      }
    }
  }

  int n, t;
  cin >> n >> t;
  vector h(t, vector<u64>(n));
  for (int r = 0; r < t; r++) {
    for (int c = 0; c < n; c++) {
      cin >> h[r][c];
      h[r][c]--;
    }
  }

  // 通常の掃き出し（pop_backの都合上、右から）
  vector<int> use(t, -1);
  for (int c0 = n - 1; c0 >= 0; c0--) {
    int r0 = -1;
    for (int r = 0; r < t; r++) {
      if (h[r][c0] == 0 || use[r] != -1)
        continue;
      use[r] = c0;
      r0 = r;
      break;
    }
    if (r0 == -1)
      continue;
    u64 inv = nim_product_inv(h[r0][c0]);
    for (auto& v : h[r0])
      v = nim_product(v, inv);
    for (int r = 0; r < t; r++) {
      if (r == r0)
        continue;
      for (int c = 0; c < n; c++) {
        h[r][c] ^= nim_product(h[r0][c], h[r][c0]);
      }
    }
  }
  
  // 正方行列の生成
  vector base_a(n, vector<u64>(n));
  for (int i = 0; i < t; i++) {
    if (use[i] != -1) {
      base_a[use[i]] = h[i];
    }
  }

  mint ans = 0;
  mint mul = mint(2).pow(64);

  auto dfs = [&](auto self, vector<vector<u64>>& a, mint add, int pop, int column) -> void {
    if (column < 0) {
      ans += pop % 2 ? -add : add;
      return;
    }

    // この列を消さない
    auto a0 = a;
    mint add0 = add;
    if (a0.back().back() == 0)
      add0 *= mul;
    a0.pop_back();
    for (auto& r : a0)
      r.pop_back();
    self(self, a0, add0, pop, column - 1);


    // この列を消す
    auto a1 = a;
    for (auto& r : a1)
      r.pop_back();
    // 別の列の要素があるなら、そこを掃き出す(O(column^2))
    for (int c0 = a1.back().size() - 1; c0 >= 0; c0--) {
      if (a1.back()[c0]) {
        u64 ainv = nim_product_inv(a1.back()[c0]);
        for (auto& v : a1.back())
          v = nim_product(v, ainv);
        for (int r = 0; r < a1.size(); r++) {
          for (int c = 0; c < a1[r].size(); c++) {            
            if (r == c0) {
              if (a1[r][c0] != a1.back()[c0])
                a1[r][c] ^= a1.back()[c];
            }
            else {
              a1[r][c] ^= nim_product(a1.back()[c], a1[r][c0]);
            }
          }
        }
        break;
      }
    }
    a1.pop_back();
    self(self, a1, add, pop + 1, column - 1);
    return;
  };
  dfs(dfs, base_a, 1, 0, n - 1);
  cout << ans.val() << endl;
}
0