← 返回题目列表

AtCoder · abc288_h

Ex. 一个无名的计数问题

中文机器翻译题面 查看原题

分数: 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 如果恰好是其中之一 k- 第最低位 A 和 B is 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