#1011040 (C++23) No.2907 Business Revealing Dora Tiles

提出ソース

結果

問題	No.2907 Business Revealing Dora Tiles
ユーザー	👑 amentorimaru
提出日時	2024-09-17 00:31:03
言語	C++23 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 6,816 KB
testcase_01	AC	3 ms 6,812 KB
testcase_02	AC	3 ms 6,944 KB
testcase_03	AC	46 ms 6,940 KB
testcase_04	AC	31 ms 6,944 KB
testcase_05	AC	5 ms 6,940 KB
testcase_06	AC	4 ms 6,944 KB
testcase_07	AC	21 ms 6,940 KB
testcase_08	AC	18 ms 6,944 KB
testcase_09	AC	4 ms 6,944 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	AC	32 ms 6,940 KB
testcase_12	AC	3 ms 6,940 KB
testcase_13	AC	4 ms 6,944 KB
testcase_14	AC	4 ms 6,940 KB
testcase_15	AC	4 ms 6,940 KB
testcase_16	AC	4 ms 6,940 KB
testcase_17	AC	3 ms 6,944 KB
testcase_18	AC	7 ms 6,940 KB
testcase_19	AC	4 ms 6,940 KB
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	32 ms 6,944 KB
testcase_22	AC	6 ms 6,940 KB
testcase_23	AC	53 ms 6,944 KB
testcase_24	AC	81 ms 6,940 KB
testcase_25	AC	79 ms 6,940 KB
testcase_26	AC	80 ms 6,944 KB
testcase_27	AC	80 ms 6,940 KB
testcase_28	AC	80 ms 6,940 KB
testcase_29	AC	113 ms 6,944 KB
testcase_30	AC	79 ms 6,944 KB
testcase_31	AC	80 ms 6,944 KB
testcase_32	AC	80 ms 6,940 KB
testcase_33	AC	79 ms 6,940 KB
testcase_34	AC	79 ms 6,944 KB
testcase_35	AC	111 ms 6,944 KB
testcase_36	AC	80 ms 6,940 KB
testcase_37	AC	79 ms 6,940 KB
testcase_38	AC	79 ms 6,940 KB
testcase_39	AC	79 ms 6,940 KB
testcase_40	AC	79 ms 6,940 KB
testcase_41	AC	96 ms 6,944 KB
testcase_42	AC	79 ms 6,944 KB
testcase_43	AC	111 ms 6,940 KB
testcase_44	AC	123 ms 6,940 KB
testcase_45	AC	197 ms 6,944 KB
testcase_46	AC	106 ms 6,940 KB
testcase_47	AC	69 ms 6,940 KB
testcase_48	AC	74 ms 6,944 KB
testcase_49	AC	202 ms 6,940 KB
testcase_50	AC	170 ms 6,944 KB
testcase_51	AC	14 ms 6,940 KB
testcase_52	AC	80 ms 6,944 KB
testcase_53	AC	103 ms 6,940 KB
testcase_54	AC	52 ms 6,944 KB
testcase_55	AC	103 ms 6,940 KB
testcase_56	AC	104 ms 6,944 KB
testcase_57	AC	105 ms 6,944 KB
testcase_58	AC	100 ms 6,940 KB
testcase_59	AC	97 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード