atcoder#ABC288H. [ABC288Ex] A Nameless Counting Problem

[ABC288Ex] A Nameless Counting Problem

题目描述

下記の 2 2 つの条件をともに満たす長さ N N の整数列 A = (A1, A2, , AN) A\ =\ (A_1,\ A_2,\ \ldots,\ A_N) の個数を 998244353 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,\ B のビットごとの排他的論理和 A  B A\ \oplus\ B は、以下のように定義されます。 - A  B A\ \oplus\ B を二進表記した際の 2k 2^k (k  0 k\ \geq\ 0 ) の位の数は、A, B A,\ B を二進表記した際の 2k 2^k の位の数のうち一方のみが 1 1 であれば 1 1 、そうでなければ 0 0 である。

例えば、3  5 = 6 3\ \oplus\ 5\ =\ 6 となります (二進表記すると: 011  101 = 110 011\ \oplus\ 101\ =\ 110 )。

输入格式

入力は以下の形式で標準入力から与えられる。

N N M M X X

输出格式

答えを出力せよ。

题目大意

给定 NNMMXX ,询问有多少个长度为 NN 的非负整数序列满足以下条件:

0A1A2...ANM0\le A_1\le A_2\le ...\le A_N\le M

A1A2...AN=XA_1\oplus A_2\oplus...\oplus A_N=X

其中 \oplus 是异或操作,答案对 998244353998244353 取模。( 1N2001\le N\le 2000M<2300\le M\lt 2^{30}0X<2300\le X\lt 2^{30} )

3 3 2
5
200 900606388 317329110
788002104

提示

制約

  • 1  N  200 1\ \leq\ N\ \leq\ 200
  • 0  M < 230 0\ \leq\ M\ \lt\ 2^{30}
  • 0  X < 230 0\ \leq\ X\ \lt\ 2^{30}
  • 入力はすべて整数

Sample Explanation 1

問題文中の 2 2 つの条件をともに満たす長さ N N の整数列 A A は、$ (0,\ 0,\ 2),\ (0,\ 1,\ 3),\ (1,\ 1,\ 2),\ (2,\ 2,\ 2),\ (2,\ 3,\ 3) $ の 5 5 個です。