#AT2468. Ex - A Nameless Counting Problem
Ex - A Nameless Counting Problem
当前没有测试数据。
Ex - A Nameless Counting Problem
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:
Output
Print the answer.
3 3 2
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)$.
200 900606388 317329110
788002104