#P17272. [2025年南开中学集训]异或运算

[2025年南开中学集训]异或运算

异或运算(xor)

题目描述

小 C 对异或运算很感兴趣。

他给了你三个整数 n,m,xn,m,x,你需要找到有多少个长度为 nn 的序列 aa,满足:

  • 0≤a1≤a2≤⋯≤an≤m0\le a_1\le a_2\le \cdots\le a_n\le m;
  • a1⊕a2⊕⋯⊕an=xa_1\oplus a_2\oplus\cdots\oplus a_n=x。

其中 ⊕\oplus 是二进制下的异或操作,为了避免高精度运算,答案对 998244353998244353 取模。

输入格式

一行四个整数 C,n,m,xC,n,m,x,表示测试点编号和题目给定参数,在样例中 C=0C=0。

输出格式

一行一个整数,表示答案。

样例 1

输入

0 3 3 2

输出

5

样例 1 解释

合法的数组有

(0,0,2)、(0,1,3)、(1,1,2)、(2,2,2)、(2,3,3),

一共 5 个。

数据范围

对于 100% 的数据,满足 1≤n≤1051\le n\le 10^5,0≤m<2300\le m<2^{30},0≤x<2300\le x<2^{30}。

测试点编号 n≤n\le m,x≤m,x\le 特殊性质
1~2 10210^2 无
3~4 10310^3
5~8 10 230−12^{30}-1
9~13 200
14~15 A
16~17 10510^5
18~21 10310^3 无
22~25 10510^5
  • 特殊性质 A:输入数据保证 m=xm=x。