102887: [AtCoder]ABC288 Ex - A Nameless Counting Problem
Description
Score : $600$ points
Problem Statement
Print the number of integer sequences of length $N$, $A = (A_1, A_2, \ldots, A_N)$, that satisfy both of the following conditions, modulo $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$
Here, $\oplus$ denotes bitwise XOR.
What is bitwise XOR?
The bitwise XOR of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows.
- When $A \oplus B$ is written in binary, the $k$-th lowest bit ($k \geq 0$) is $1$ if exactly one of the $k$-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.
Constraints
- $1 \leq N \leq 200$
- $0 \leq M \lt 2^{30}$
- $0 \leq X \lt 2^{30}$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $X$
Output
Print the answer.
Sample Input 1
3 3 2
Sample Output 1
5
Here are the five sequences of length $N$ that satisfy both conditions in the statement: $(0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3)$.
Sample Input 2
200 900606388 317329110
Sample Output 2
788002104
Input
题意翻译
给定 $N$，$M$，$X$ ，询问有多少个长度为 $N$ 的非负整数序列满足以下条件： $0\le A_1\le A_2\le ...\le A_N\le M$ $A_1\oplus A_2\oplus...\oplus A_N=X$ 其中 $\oplus$ 是异或操作，答案对 $998244353$ 取模。( $1\le N\le 200$，$0\le M\lt 2^{30}$ ，$0\le X\lt 2^{30}$ )Output
分数：$600$分
问题描述
对于长度为$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$定义如下。
- 当$A \oplus B$用二进制表示时，第$k$个最低位（$k \geq 0$）为$1$，如果$A$和$B$的第$k$个最低位中恰好有一个为$1$，否则为$0$。
约束条件
- $1 \leq N \leq 200$
- $0 \leq M \lt 2^{30}$
- $0 \leq X \lt 2^{30}$
- 输入中的所有值都是整数。
输入
输入将从标准输入中以下格式给出：
$N$ $M$ $X$
输出
打印答案。
样例输入1
3 3 2
样例输出1
5
以下是满足声明中两个条件的长度为$N$的五个序列：$(0, 0, 2), (0, 1, 3), (1, 1, 2), (2, 2, 2), (2, 3, 3)$。
样例输入2
200 900606388 317329110
样例输出2
788002104