nim mul

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <tuple>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

using namespace std;

typedef unsigned int nimber;

nimber nim_mul_rec(nimber x, nimber y, int m) {
  if (!x || !y) return 0;
  if (m == 0) return 1;
  int n = 1 << (m - 1);
  nimber a = x >> n, b = x & ((1u << n) - 1u),
         c = y >> n, d = y & ((1u << n) - 1u);
  nimber ac = nim_mul_rec(a, c, m - 1), bd = nim_mul_rec(b, d, m - 1);
  return ((nim_mul_rec(a ^ b, c ^ d, m - 1) ^ bd) << n) + (nim_mul_rec(1u << (n - 1), ac, m - 1) ^ bd);
}

namespace F_2_16 {

const nimber R = 258;

nimber power_table[1 << 16];
int index_table[1 << 16];

void init() {
  nimber cur = 1;
  for (int i = 0; i < (1 << 16) - 1; ++i) {
    power_table[i] = cur;
    index_table[cur] = i;
    cur = nim_mul_rec(cur, R, 4);
  }
}

nimber nim_mul16(nimber x, nimber y) {
  if (!x || !y) return 0;
  int u = index_table[x], v = index_table[y];
  if ((u += v) >= (1 << 16) - 1) u -= (1 << 16) - 1;
  return power_table[u];
}

}

nimber nim_mul32(nimber x, nimber y) {
  if (!x || !y) return 0;
  nimber a = x >> 16, b = x & ((1u << 16) - 1u),
         c = y >> 16, d = y & ((1u << 16) - 1u);
  nimber ac = F_2_16::nim_mul16(a, c), bd = F_2_16::nim_mul16(b, d);
  return ((F_2_16::nim_mul16(a ^ b, c ^ d) ^ bd) << 16) + (F_2_16::nim_mul16(1u << 15, ac) ^ bd);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  F_2_16::init();



  return 0;
}