题目描述
给定一个长度为 $n$ 的序列 $A$，求有多少个子序列满足所选下标集合为 ${b_1,b_2,\dots,b_k}$ 时 $a_{b_1}\ge a_{b_2}\ge\dots\ge a_{b_{k-1}}\ge a_{b_k}$ 且 $\prod_{i=2}^kC_{a_{i-1}}^{a_i}\equiv 1\pmod 2$，输出答案模 $10^9+7$ 的值。
$1\le n\le 211985$，$1\le a_i\le 233333$。所有的 $a_i$ 互不相同，也就是说不存在 $i,j$ 同时满足 $1\le i\lt j\le n$ 和 $a_i=a_j$。
算法分析
分析组合数连乘的式子，由于模数很小为 $2$，考虑使用 Lucas 定理求解。
这里需要想到，Lucas 定理拆分后的组合数中每一项只可能有四种情况，即 $C_0^0=C_1^0=C_1^1=1$ 或 $C_0^1=0$，这表明相邻两个数二进制拆分后不存在 $a_i$ 上的一位大于 $a_{i-1}$ 上对应的位，看作集合的话说明 $a_i$ 是 $a_{i-1}$ 的子集，也就是 $a_{i-1}\bigcap a_i=a_i$，同时也满足了这是一个不下降的子序列，因为一定有 $a_{i-1}\ge a_i$。
一个暴力的做法是考虑 DP，定义 $f[i]$ 表示处理以第 $i$ 个数为末尾的方案数，枚举上一个选择的数的下标 $j$ 即可转移。时间复杂度为 $O(n^2)$，期望得分 $70$ 分。
注意到前面选取的数一定是当前数超集（二进制状态下看作集合时），可以重新定义 DP 方程，设 $f[i][j]$ 表示前 $i$ 个数中，当前子序列末尾的数为 $j$（可以看作集合）时的方案数，转移只需要枚举子集就可以了，因为 $n$ 比 $a_i$ 的最大值要小，而 $233333\lt 2^{18}$，因此总的时间复杂度为 $O(3^{18})$。
很多网上的题解到这里就结束了，但这个复杂度显然是不靠谱的，可以通过拆位的方法对其进行优化。
枚举 $i$ 后可以将第一维省略掉，设 $f[x][y]$ 表示低 $9$ 位为 $y$ 且高 $9$ 位为 $x$ 的超集的方案数，这样在每次查询时就只需枚举低 $9$ 位的超集，每次修改时只需枚举高 $9$ 位的子集，时间复杂度为 $O(6^9)$。
怎么枚举超集呢？只需枚举补集的子集再取补集就可以了。
代码实现
1 |
|