AT_abc288_h [ABC288Ex] A Nameless Counting Problem

题目描述

请输出满足以下两个条件的长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$ 的个数，并对 $998244353$ 取模。

• $0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq M$
• $A_1 \oplus A_2 \oplus \cdots \oplus A_N = X$

这里，$\oplus$ 表示按位异或运算。

什么是按位异或？对于非负整数 $A, B$，它们的按位异或 $A \oplus B$ 定义如下：对于二进制表示下的每一位 $2^k$（$k \geq 0$），如果 $A$ 和 $B$ 在该位上恰有一个为 $1$，则结果在该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $X$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 3 2

输出 #1

5

输入输出样例 #2

输入 #2

200 900606388 317329110

输出 #2

788002104

说明/提示

限制条件

• $1 \leq N \leq 200$
• $0 \leq M < 2^{30}$
• $0 \leq X < 2^{30}$
• 输入均为整数

样例解释 1

满足题目中两个条件的长度为 $N$ 的整数序列 $A$ 有 $(0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3)$ 共 $5$ 个。

由 ChatGPT 4.1 翻译