atcoder#ABC278H. [ABC278Ex] make 1
[ABC278Ex] make 1
题目描述
次の条件を満たす非負整数列 を 良い数列 と呼びます。
- の(連続とは限らない)非空な部分列 であって、 のすべての要素のビットごとの xor が であるようなものが存在する。
空の数列 、および 以上 未満の整数が 1 つずつ書かれた 枚のカードがあります。
あなたは次の操作を が良い数列になるまで繰り返します。
- カードを 1 枚自由に選び、カードに書かれている数を の末尾に追加する。そして選んだカードを食べる。(食べたカードはその後選ぶことはできない)
操作後の としてあり得る数列のうち長さが であるものは何種類ありますか? 答えを で出力してください。
ビットごとの xor とは? 非負整数 のビット単位 xor 、 は、以下のように定義されます。 - を二進表記した際の () の位の数は、 を二進表記した際の の位の数のうち一方のみが であれば 、そうでなければ である。
例えば、 となります (二進表記すると: )。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを出力せよ。
题目大意
一个非负整数序列 是好的,当且仅当 存在一个非空子序列 ,满足 中所有元素的异或和为 。
有一个初始为空的序列 ,以及 张写着数字的卡片;卡片上的数字取遍 中的整数。你可以自由选择一张卡片,将这张卡片上的数字放在 序列的末尾,并删除这张卡片,以后不能再选择它。你会一直进行这个操作,当 成为好的序列后停止。
给定 ,求停止操作时长度为 的不同 序列数。答案对 取模。
$1\le n\le 2\times 10^5, \ 1\le m \le 10^7,\ n\le 2^m$。
2 2
5
2022 1119
293184537
200000 10000000
383948354
提示
制約
- は整数
Sample Explanation 1
操作後の としてあり得る数列のうち長さが であるものは次の 種類です。 - - - - -