33OJ
登录 注册

#P17766. 「LDOI R2」位运算 / Bit

    ID: 20376 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>贪心洛谷原创O2优化位运算构造洛谷月赛

「LDOI R2」位运算 / Bit

Background

One day,

https://www.luogu.com.cn/user/766573
following C++ code involving bitwise operations:

(11l<<i)

The problem provider, concerned about making similar mistakes, created this bitwise operation problem:

Problem Description

Given four integers n,x,y,zn,x,y,z, you have to construct an array of nn integers ai (1≤i≤n)a_i\ (1\le i\le n), such that $\mathop{\operatorname{and}}\limits_{i=1}^n a_i=x,\mathop{\operatorname{or}}\limits_{i=1}^n a_i=y,\mathop{\operatorname{xor}}\limits_{i=1}^n a_i=z$ and ∏i=1nai\prod\limits_{i=1}^na_i is maximized. In the above description, $\operatorname{and},\operatorname{or},\operatorname{xor}$ represent AND, OR, XOR in bitwise operations.

If such an array aia_i exists, output max⁡∏i=1nai\max\prod\limits_{i=1}^n a_i modulo 998244853998244\red{8}53; otherwise output −1-1.

Input Format

There are multiple test cases for this problem.

The first line contains an integer TT, representing the number of test cases.

The next TT lines each contain four non-negative integers n,x,y,zn,x,y,z.

Output Format

For each test case:

  • If no solution exists, output −1-1.

  • Otherwise, output one integer: max⁡∏i=1nai\max\prod\limits_{i=1}^na_i modulo 998244853998244\red{8}53.

2
3 2 7 6
8 6 55 36
54
-1
4
9 2 7 6
18 3 5 0
4 1 59 24
841039 0 7 7

6353046
-1
1464561
906098946

Hint

Explanation

For the first test case in the first sample, choose the numbers 3,3,63,3,6. Since 3and⁡3and⁡6=23\operatorname{and}3\operatorname{and}6=2, 3or⁡3or⁡6=73\operatorname{or}3\operatorname{or}6=7, 3xor⁡3xor⁡6=63\operatorname{xor}3\operatorname{xor}6=6, the conditions are satisfied, and it can be shown that the product 5454 is maximal.

For the second test case in the first sample, there is no sequence aa that satisfies the conditions.

Constraints

Test Case n≤n \le x,y,z<x,y,z < T≤T \le
11 22 2302^{30} 10510^5
22 44 242^4 100100
3,43, 4 5050 ^ ^
5,65, 6 ^ 262^6
7,87, 8 10210^2 2302^{30}
9,109, 10 10410^4 ^
11,1211, 12 101810^{18} 2602^{60} 10310^3
13∼1513 \sim 15 ^ 10410^4
16∼1816 \sim 18 10510^5
19,2019, 20 5×1055 \times 10^5

For all test cases, 1≤n≤10181\le n \le 10^{18}, 0≤x,y,z<2600\le x,y,z < 2^{60}, 1≤T≤5×1051\le T \le 5 \times 10^5.

Hint

Please pay attention to the impact of constant factors on program efficiency when implementing the code.

The input/output may be large, please use fast input/output methods. Here is an input template using fread:

typedef unsigned long long ull;
char buf[1<<20],*p1,*p2;
char gc() {
	if(p1==p2) p2=(p1=buf)+fread(buf,1,1<<20,stdin);
	return *p1++;
}
ull rd() {
	ull s=0;
	char c=gc();
	while(c<48) c=gc();
	while(c>47) s=s*10+(c^48), c=gc();
	return s;
}

Call the function rd() to read a 6464 bit unsigned integer.