102887: [AtCoder]ABC288 Ex - A Nameless Counting Problem

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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.
For instance, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

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$。
例如,$3 \oplus 5 = 6$(用二进制表示为:$011 \oplus 101 = 110$)。

约束条件

  • $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

加入题单

上一题 下一题 算法标签: