4054 序列

题面

内容

给定 $n, m$，求所有长为 $n$ 的序列 $a$，满足 $0 \le a_i \le m, \sum\limits_{i = 1}^n a_i = m$ 的序列 $a$ 的价值之和，对 $10^9 + 9$ 取模的结果。

这里一个序列的价值定义为它所有元素的异或和。

输入

输入一行两个整数 $n, m$。

输出

输出一行一个整数，表示价值和模 $10^9 + 9$ 的结果。

样例1

输入

2 5

输出

22

样例2

输入

3 5

输出

63

样例3

输入

4 18

输出

12712

样例4

输入

90 98

输出

359887814

提示

对于 $100 \%$ 的数据，满足 $2 \le n \le 10^3, 0 \le m \le 10^9$。

样例 $1$ 解释：

序列 $a$ 为 $(0, 5)$，异或和为 $0 \oplus 5 = 5$；

序列 $a$ 为 $(1, 4)$，异或和为 $1 \oplus 4 = 5$；

序列 $a$ 为 $(2, 3)$，异或和为 $2 \oplus 3 = 1$；

序列 $a$ 为 $(3, 2)$，异或和为 $3 \oplus 2 = 1$；

序列 $a$ 为 $(4, 1)$，异或和为 $4 \oplus 1 = 5$；

序列 $a$ 为 $(5, 0)$，异或和为 $5 \oplus 0 = 5$；

和为 $5 + 5 + 1 + 1 + 5 + 5 = 22$。

思路

首先题意是让你找出所有的序列，这个序列满足长度为$n$序列和等于$m$，序列中的每个数都满足$\in{[0,m]}$的范围，该序列的价值为该序列中所有的数的异或和，答案是所有情况的异或和的求和$\pmod{1e9+9}$。

我们可以来看序列中$n$个数和$m$的二进制表示，定义$f_{i,j}$为考虑完前$i$位，且第$i$位的和等于$m$的这一位，下一位进位为$j$的方案数，$g_{i,j}$表示考虑完前$i$位，且第$i$位的和等于$m$的这一位，下一位进位位$j$的所有方案异或和的求和。

因为我们要保证序列和为$m$，所以我们要保证二进制下每一位加起来都等于$m$的这一位。

然后我们枚举一个$k$代表第$i$位我要在$1\sim{n}$中填多少个1。

那么$f_{i+1,{\lfloor\frac{j+k}{2}}\rfloor}=f_{i,j}\times{C(^{n}_{k})}$，其中$C$为组合数，意为原来的方案数，在$i$这位又产生了$C(^{n}{k})$种可能，由于相互独立性，因此下一位的方案数是它们相乘。

假如$k$是偶数，那么这一位异或起来一定是$0$，所以不会产生新的贡献，有的只是新的情况，所以就相当于有若干个$g_{i,j}$加了起来组成了新的状态，也就是：

$g_{i+1,{\lfloor\frac{j+k}{2}}\rfloor}=g_{i,j}\times{C(^{n}_{k})}$

假如$k$是奇数，那么这一位异或起来一定是$1$，而第$i+1$位加一，产生的贡献是$2^{i+1}$，所以会产生情况数$\times$每种情况的贡献，也就是：

$g_{i+1,{\lfloor\frac{j+k}{2}\rfloor}}=g_{i,j}+2^{i+1}\times{f_{i,j}}\times{C(^n_k)}$

所以最后的答案就是$g_{logm,0}$。