标签：count aligned sum 2i glass 2n 酒杯 NOD2308B binom

NOD2308B. 酒杯（glass）

题意

有一棵 \(n\) 层的满二叉树，有 \(m\) 次操作，每次操作从 \(2^n-1\) 个节点中随机选择一个节点染黑（可以重复染色），问使得每一层都至少有一个节点被染黑的方案数。\(n,m\le 2000\)，答案对 \(10^9 + 7\) 取模。

solution

%%% 蔡队

代码未编写，因此过程可能推错，请自行辨别 and 欢迎指出

显然问题可以简化成有 \(n\) 个点，第 \(i\) 个点有 \(2^{i-1}\) 种方式可以被染黑，问所有点都被染黑的方案数。

暴力就是枚举每次操作染了哪个点。

直接统计染上所有点的方案数是不好统计的。但是算至多可以染某些点的方案数是好算的。

考虑容斥。用点集 \(S\) 表示不允许染 \(S\) 里面的点。

子集枚举。

\[\begin{aligned} ans & =\sum_{S\subseteq [n]}(-1)^{|S|} (\sum_{i \not \in S} 2^i)^m\\ & = \sum_{S=0}^{2^n-1} (-1)^{count(S)} (2^n-1-S)^m \end{aligned} \]

设 \(S\) 表示允许染色的点集，那么有更加优美的式子：

\[f(n,m)=\sum_{S=0}^{2^n-1} (-1)^{n-count(S)} S^m \]

换个名字，写成：

\[f(n,m)=\sum_{i=0}^{2^n-1} (-1)^{n-count(i)} i^m \]

发现 \(f(n,m)\) 的个数是 \(nm\) 的，考虑变成递推转移。

假设我们考虑完前 \(n-1\) 个点，然后再加上第 \(n\) 个点，假设我们的 \(i\) 是把序号小的放在低位，有：

若 \(i\) 是把序号大的放在低位，式子会变好看吗？

\[f(n,m)=\sum_{i=0}^{2^{n-1}-1} (-1)^{n-count(i)} ((2i)^m - (2i+1)^m) \]

表示子集枚举前 \(i\) 个点的选择状态，乘方案数的时候枚举是否选择第 \(n\) 个数。\(2i\) 的状态表示不选，\(2i+1\) 的状态表示选择。

根据二项式定理：\((x+y)^n = \sum_{i=0}^n \binom{n}{i} x^{n-i}y^i\)。

把 \((2i+1)^m\) 拆开，变成 \(\sum_{k=0}^m \binom{m}{k} (2i)^k\)。

有：

\[\begin{aligned} f(n,m) & =\sum_{i=0}^{2^{n-1}-1} (-1)^{n-count(i)} (\sum_{k=0}^{m-1} - \binom{m}{k}(2i)^k )\\ & =\sum_{i=0}^{2^{n-1}-1} (-1)^{n-count(i)-1} (\sum_{k=0}^{m-1} \binom{m}{k}(2i)^k )\\ & =\sum_{k=0}^{m-1} \binom{m}{k} 2^k \sum_{i=0}^{2^{n-1}-1} (-1)^{n-count(i)-1} i^k\\ & =\sum_{k=0}^{m-1} \binom{m}{k} 2^k f(n-1,k) \end{aligned} \]

至此你获得了转移复杂度为 \(O(m)\) 的递推式。状态是 \(O(nm)\)，总时间复杂度是 \(O(nm^2)\)。

边界条件是 \(f(0,0)=1\)。

蔡队的分段打表方法（很有学习意义）

发现 \(f(n,m)\) 只和 \(f(n-1,k)\) 有关，因此对于第一维每隔 \(B\) 打一个长度为 \(m\) 的表。

然后发现空间不够。为什么 cplusoj 只能上传 50kb 的代码？解决方法是把表压成字符，使用表的时候进行解码操作。

题解提出倍增优化。

也许突破口是 \(f(n,m)\) 的具体意义感觉可以倍增？或许是因为 \(f(n,m)\) 只和 \(f(n-1)\) 有关，所以想要优化第一维的递推？类似于快速幂？

根据 \(f(2n,m)\) 的具体意义。考虑子集枚举前 \(n\) 个数的选择状态，乘方案数的时候枚举后 \(n\) 个数的选择状态。

\[\begin{aligned} f(2n,m) & =\sum_{i=0}^{2^{2n}-1} (-1)^{2n-count(i)} i^m\\ & = \sum_{i=0}^{2^n-1} (-1)^{n-count(i)} (\sum_{j=0}^{2^n-1} (-1)^{n-count(j)} (i+2^n j)^m)\\ & = \sum_{i=0}^{2^n-1} (-1)^{n-count(i)}(\sum_{j=0}^{2^n-1} (-1)^{n-count(j)} (\sum_{k=0}^m \binom{m}{k} i^{m-k} 2^{nk} j^k))\\ & = \sum_{k=0}^m \binom{m}{k} 2^{nk} \sum_{i=0}^{2^n-1} (-1)^{n-count(i)} i^{m-k} \sum_{j=0}^{2^n-1} (-1)^{n-count(j)} j^k \\ & = \sum_{k=0}^m \binom{m}{k} 2^{nk} f(n,m-k)f(n,k) \end{aligned} \]

好像……解决啦。Hooray!

但是 \(n\) 不一定是 \(2\) 的幂次怎么办呢？能否推广？

\[\begin{aligned} f(2n+n,m) & =\sum_{i=0}^{2^{2n}-1} (-1)^{2n-count(i)} (\sum_{j=0}^{2^n-1} (-1)^{n-count(j)} (i+2^{2n} j)^m)\\ & =\sum_{i=0}^{2^{2n}-1} (-1)^{2n-count(i)} (\sum_{j=0}^{2^n-1} (-1)^{n-count(j)} (\sum_{k=0}^{m} \binom{m}{k} i^{m-k} 2^{2nk}j^k ))\\ & =\sum_{k=0}^{m} \binom{m}{k} 2^{2nk} \sum_{i=0}^{2^{2n}-1} (-1)^{2n-count(i)} i^{m-k} \sum_{j=0}^{2^n-1} (-1)^{n-count(j)} j^k\\ & =\sum_{k=0}^{m} \binom{m}{k} 2^{2nk} f(2n,m-k) f(n,k) \end{aligned} \]

太优美了！可以推广！

那么就做完了，对 \(n\) 这一维倍增，时间复杂度 \(O(nm \log n)\)。

code

待订正。

标签：count,aligned,sum,2i,glass,2n,酒杯,NOD2308B,binom
From： https://www.cnblogs.com/liyixin0514/p/18501396