CF623E Transforming Sequence 做题记录

对于一个整数序列 $\{a_1, a_2, \ldots, a_n\}$，我们定义它的变换为 $\{b_1, b_2, \ldots, b_n\}$，其中 $b_i = a_1 | a_2 | \ldots | a_i$，其中 $|$ 表示二进制按位或运算。

现在求有多少个长为 $n$ 的序列 $a$，满足 $1\leq a_i \leq 2^k - 1$，使得它的变换 $b$ 是严格单调递增的，对 $10^9+7$ 取模。

$1\leq n \leq 10^{18}$，$1\leq k \leq 3 \times 10^4$。

我们设 $dp_{i,j,0/1}$ 表示序列有 $i$ 个数，当前或和第 $j$ 位（二进制）是 $0/1$ 的方案数

好难转移啊/ll

如果设 $dp_{i,j}$ 表示序列有 $i$ 个数，当前或和为 $j$ 的方案数呢？

那么我们可以枚举 $j$ 的二进制中 $1$ 的个数来转移！

所以说正确的状态应该是 $dp_{i,j}$ 表示序列有 $i$ 个数，当前或和二进制有 $j$ 个 $1$。

推一下柿子：

$dp_{i,j}=\sum\limits_{l=0}^j\dbinom{j}{l}dp_{i-1,l}2^l$

这个柿子的意思是，枚举前 $i-1$ 项的或和有多少个 $1$ 和这些 $1$ 在哪里，然后第 $i$ 项的剩下 $j-l$ 个 $1$ 的位置必须是 $1$，但是 $l$ 个 $1$ 的位置可以是 $0$ 也可以是 $1$。

拆组合数：

$dp_{i,j}=j!\sum\limits_{l=0}^j\dfrac{dp_{i-1,l}2^l}{l!}\dfrac{1}{(j-l)!}$

考虑换一种转移方式，有：

$dp_{a+b,j}=\sum\limits_{l=0}^j \dbinom{j}{l}dp_{a,l}dp_{b,j-l}2^{bl}$

这个柿子的意思是，枚举前 $a$ 项的或和有多少个 $1$ 和这些 $1$ 在哪里，然后剩下 $b$ 项补足前 $a$ 项没有的 $1$，并且这 $b$ 项的被前 $a$ 项占用的那些位置可以填 $0/1$。

然后拆一下组合数：

$dp_{a+b,j}=j!\sum\limits_{l=0}^j\dfrac{2^{bl}dp_{a,l}}{l!}\dfrac{dp_{b,j-l}}{(j-l)!}$

也就是说，我们可以这样倍增转移：

$\begin{cases}dp_{n,i}=i!\sum\limits_{j=0}^i\dfrac{dp_{n-1,j}2^j}{j!}\dfrac{1}{(i-j)!}\\dp_{2n,i}=i!\sum\limits_{j=0}^i\dfrac{2^{nj}dp_{n,j}}{j!}\dfrac{dp_{n,i-j}}{(i-j)!}\end{cases}$

好了，用 MTT 优化就行。