verify/nim_product_64.test.cpp

View this file on GitHub · Last update: 2026-07-25 01:16:11-07:00

Problem: https://judge.yosupo.jp/problem/nim_product_64

Depends on

• nim_prod.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/nim_product_64

#include <bits/stdc++.h>
#include <cassert>

#include "nim_prod.hpp"

constexpr nim_prod_t nimProd;

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int T; std::cin >> T;
	while (T--) {
		uint64_t A, B; std::cin >> A >> B;
		std::cout << nimProd(A, B) << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>
#line 1 "verify/nim_product_64.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/nim_product_64

#line 5 "verify/nim_product_64.test.cpp"

#line 2 "src/nim_prod.hpp"

#line 5 "src/nim_prod.hpp"

// Usage:
//   constexpr nim_prod_t nimProd;
// C++20:
//   constinit nim_prod_t nimProd;
struct nim_prod_t {
	uint64_t bit_prod[64][64]{};
	constexpr nim_prod_t() {
		for (int i = 0; i < 64; i++) {
			for (int j = 0; j < 64; j++) {
				if ((i & j) == 0) {
					bit_prod[i][j] = uint64_t(1) << (i|j);
				} else {
					int a = (i&j) & -(i&j);
					bit_prod[i][j] = bit_prod[i ^ a][j] ^ bit_prod[(i ^ a) | (a-1)][(j ^ a) | (i & (a-1))];
				}
			}
		}
	}
	constexpr uint64_t operator () (uint64_t x, uint64_t y) const {
		uint64_t res = 0;
		for (int i = 0; i < 64 && (x >> i); i++)
			if ((x >> i) & 1)
				for (int j = 0; j < 64 && (y >> j); j++)
					if ((y >> j) & 1)
						res ^= bit_prod[i][j];
		return res;
	}
};
#line 7 "verify/nim_product_64.test.cpp"

constexpr nim_prod_t nimProd;

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int T; std::cin >> T;
	while (T--) {
		uint64_t A, B; std::cin >> A >> B;
		std::cout << nimProd(A, B) << '\n';
	}

	return 0;
}

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
// src/nim_prod.hpp
struct nim_prod_t{
uint64_t bit_prod[64][64]{};
constexpr nim_prod_t(){
for(int i=0;i<64;i++){
for(int j=0;j<64;j++){
if((i&j)==0){
bit_prod[i][j]=uint64_t(1)<<(i|j);
}else{
int a=(i&j)&-(i&j);
bit_prod[i][j]=bit_prod[i^a][j]^bit_prod[(i^a)|(a-1)][(j^a)|(i&(a-1))];
}
}
}
}
constexpr uint64_t operator()(uint64_t x,uint64_t y)const{
uint64_t res=0;
for(int i=0;i<64&&(x>>i);i++)
if((x>>i)&1)
for(int j=0;j<64&&(y>>j);j++)
if((y>>j)&1)
res^=bit_prod[i][j];
return res;
}
};
// verify/nim_product_64.test.cpp
constexpr nim_prod_t nimProd;
int main(){
std::ios_base::sync_with_stdio(false),std::cin.tie(nullptr);
int T;std::cin>>T;
while(T--){
uint64_t A,B;std::cin>>A>>B;
std::cout<<nimProd(A,B)<<'\n';
}
return 0;
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

Test cases

Env	Name	Status	Elapsed	Memory
g++-sanitizer	example_00	AC	14 ms	8 MB
g++-sanitizer	large_00	AC	5584 ms	10 MB
g++-sanitizer	large_few_00	AC	577 ms	10 MB
g++-sanitizer	power_of_two_00	AC	17 ms	8 MB
g++-sanitizer	random_00	AC	2998 ms	10 MB
g++-sanitizer	random_01	AC	3093 ms	10 MB
g++-sanitizer	random_few_00	AC	310 ms	10 MB
g++-sanitizer	random_few_01	AC	306 ms	10 MB
g++-sanitizer	small_00	AC	333 ms	10 MB
g++-sanitizer	small_few_00	AC	41 ms	9 MB
g++	example_00	AC	3 ms	4 MB
g++	large_00	AC	3282 ms	4 MB
g++	large_few_00	AC	334 ms	4 MB
g++	power_of_two_00	AC	3 ms	4 MB
g++	random_00	AC	2214 ms	4 MB
g++	random_01	AC	2247 ms	4 MB
g++	random_few_00	AC	224 ms	4 MB
g++	random_few_01	AC	228 ms	4 MB
g++	small_00	AC	271 ms	4 MB
g++	small_few_00	AC	24 ms	4 MB

Back to top page