atcoder#ABC288H. [ABC288Ex] A Nameless Counting Problem
[ABC288Ex] A Nameless Counting Problem
题目描述
下記の つの条件をともに満たす長さ の整数列 の個数を で割ったあまりを出力してください。
- $ 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 $
ここで、 はビットごとの排他的論理和を表します。
ビットごとの排他的論理和とは? 非負整数 のビットごとの排他的論理和 は、以下のように定義されます。 - を二進表記した際の () の位の数は、 を二進表記した際の の位の数のうち一方のみが であれば 、そうでなければ である。
例えば、 となります (二進表記すると: )。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを出力せよ。
题目大意
给定 ,, ,询问有多少个长度为 的非负整数序列满足以下条件:
其中 是异或操作,答案对 取模。( , , )
3 3 2
5
200 900606388 317329110
788002104
提示
制約
- 入力はすべて整数
Sample Explanation 1
問題文中の つの条件をともに満たす長さ の整数列 は、$ (0,\ 0,\ 2),\ (0,\ 1,\ 3),\ (1,\ 1,\ 2),\ (2,\ 2,\ 2),\ (2,\ 3,\ 3) $ の 個です。