题解：组合数奇偶性与二进制子集

问题转化

给定长度为 $n$ 的序列 $a_1,\dots,a_n$（互不相同），求满足以下条件的不上升子序列（长度 $\ge 2$）个数：

1. $b_1 < b_2 < \cdots < b_k$
2. $a_{b_1} \ge a_{b_2} \ge \cdots \ge a_{b_k}$
3. $\prod_{i=2}^k \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 = 1$（即每个组合数都是奇数，且乘积为奇数）

关键定理：Lucas 定理

$\binom{n}{m} \bmod 2 = 1$ 当且仅当 $m$ 的二进制表示是 $n$ 的二进制表示的子集，即 $m \ \&\ n = m$（按位与）。

证明：由 Lucas 定理，$\binom{n}{m} \bmod p = \prod \binom{n_i}{m_i} \bmod p$，其中 $n_i,m_i$ 是 $n,m$ 的 $p$ 进制位。对于 $p=2$，$\binom{0}{0}=1,\binom{1}{0}=1,\binom{1}{1}=1,\binom{0}{1}=0$。所以 $\binom{n}{m} \bmod 2 = 1$ 当且仅当每个二进制位满足 $m_i \le n_i$，即 $m$ 的二进制位是 $n$ 的子集。

条件转换

对于子序列 $a_{b_1} \ge a_{b_2} \ge \cdots \ge a_{b_k}$，需要 $\binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2 = 1$ 对所有 $i=2..k$ 成立。

由 Lucas 定理，这等价于 $a_{b_i}$ 的二进制位是 $a_{b_{i-1}}$ 的二进制位的子集，即 $a_{b_i} \ \&\ a_{b_{i-1}} = a_{b_i}$。

由于 $a_{b_{i-1}} \ge a_{b_i}$ 且二进制子集关系成立，实际上这等价于 $a_{b_{i-1}}$ 的二进制 1 的位置包含了 $a_{b_i}$ 的二进制 1 的位置。

转化为 DAG 路径计数

将每个数 $a_i$ 视为节点，若 $i < j$ 且 $a_i \ge a_j$ 且 $a_j \ \&\ a_i = a_j$，则从 $i$ 向 $j$ 连有向边。

我们需要统计所有长度 $\ge 2$ 的路径（即节点序列）的条数。

设 $f[i]$ 表示以 $i$ 为结尾的路径条数（路径长度至少为 1，即包含 $i$ 自身作为最后一个节点），则 $f[i] = 1 + \sum_{j \to i} f[j]$，其中 $j \to i$ 表示存在符合条件的边。

最终答案为 $\sum_{i=1}^n (f[i] - 1)$（减去长度为 1 的路径，因为我们需要长度至少为 2）。

优化边数

直接建边 $O(n^2)$ 不可行。需要利用二进制子集的性质。

条件 $a_j \ \&\ a_i = a_j$ 且 $a_i \ge a_j$（由于二进制子集蕴含 $a_i \ge a_j$，所以 $a_i \ge a_j$ 自动满足）且 $i < j$。

因此，对于每个 $a_j$，它能从前面的所有 $a_i$ 转移过来，只要 $a_i$ 的二进制包含 $a_j$ 的所有 1 位。

枚举超集

对于固定的 $a_j$，它的所有超集 $a_i$（即 $a_i \ \&\ a_j = a_j$）且 $i < j$ 都可以转移到 $a_j$。

由于 $a_i$ 互不相同，我们可以按输入顺序处理，用桶记录每个值的 $f$ 值。

但 $a_i$ 范围达到 $233333$，直接枚举超集复杂度太高。

SOS DP（子集和 DP）优化

设 $dp[mask]$ 表示当前已处理的数中，值为 $mask$ 的 $f$ 值之和（若 $mask$ 未出现则为 0）。

对于当前数 $a_j$，需要求所有超集 $mask \supseteq a_j$ 的 $dp[mask]$ 之和。

这是典型的高维前缀和（SOS DP）问题：$F[mask] = \sum_{super \supseteq mask} dp[super]$。

可以在每处理完一个数后更新 $dp[a_j]$。

具体步骤：

1. 初始化 $dp[mask]=0$，答案 $ans=0$。
2. 按输入顺序处理每个 $a_j$：
   • 计算 $sum = F[a_j]$（即所有超集的 $f$ 值之和）
   • 令 $f_j = 1 + sum$（以 $a_j$ 结尾的路径数）
   • 更新答案：$ans \leftarrow ans + (f_j - 1)$
   • 更新 $dp[a_j] = dp[a_j] + f_j$
   • 更新高维前缀和 $F$（因为 $dp$ 改变了）

高维前缀和更新

设值域 $M = \max a_i$，令 $U = 2^{\lceil \log_2 M \rceil} - 1$，一般取 $U=2^{19}-1=524287$（因为 $a_i \le 233333 < 2^{18}$）。

我们需要维护数组 $F[mask]$ 表示 $\sum_{super \supseteq mask} dp[super]$。

当 $dp[x]$ 增加 $\Delta$ 时，需要更新所有 $mask$ 满足 $mask \subseteq x$ 的 $F[mask]$ 增加 $\Delta$。

这可以用 SOS DP 的经典方法：

for(int i=0; i<B; i++) {
    for(int mask=0; mask<=U; mask++) {
        if(mask & (1<<i)) {
            dp[mask] += dp[mask ^ (1<<i)];
        }
    }
}

但这是离线做法。我们需要在线更新。

在线更新：当 $dp[x]$ 增加 $\Delta$ 时，对所有 $mask \subseteq x$ 的 $F[mask]$ 加 $\Delta$。

可以枚举 $x$ 的所有子集：$sub = x$; $sub = (sub-1) \& x$ 直到 $sub=0$。复杂度 $O(2^{popcount(x)})$。

由于 $a_i \le 233333$，二进制位数最多 18，所以枚举子集复杂度 $O(2^{18})$ 最坏，但平均较小。

但 $n$ 可达 $211985$，总复杂度 $O(n \cdot 2^{18})$ 太大。

优化：分块更新

我们不需要每次查询都重新计算 $F$，可以维护 $dp$ 数组，查询时临时计算超集和。

查询 $F[a_j]$ 时，需要计算 $\sum_{super \supseteq a_j} dp[super]$。可以枚举 $a_j$ 的所有超集：$sup = a_j$; 然后通过将 $a_j$ 的某些 0 位变成 1 来枚举超集。

但 $a_j$ 的 0 位最多 18 位，枚举超集也是 $O(2^{18})$。

折中：值域分治

注意到 $a_i \le 233333 < 2^{18}$，但实际二进制位 1 的个数不会太多。我们可以用 meet-in-the-middle。

将 18 位分成高 9 位和低 9 位。

对于数 $x$，记 $hi = x >> 9$，$lo = x \& 511$。

条件 $y \subseteq x$ 等价于 $hi_y \subseteq hi_x$ 且 $lo_y \subseteq lo_x$。

预处理数组 $cnt[hi][lo]$ 表示高 9 位为 $hi$，低 9 位为 $lo$ 的 $f$ 值。

查询时，对于 $x$，枚举所有 $hi' \supseteq hi_x$，对于每个 $hi'$，需要低 9 位 $lo' \supseteq lo_x$ 的 $cnt[hi'][lo']$ 之和。

对每个 $hi'$，预处理低 9 位的超集前缀和 $sum[hi'][mask]$。

这样查询复杂度 $O(2^{9})$，更新复杂度 $O(2^{9})$。

具体实现

设 $B=9$，$S=2^B=512$。

$dp[hi][lo]$ 表示高 9 位为 $hi$，低 9 位为 $lo$ 的 $f$ 值之和。

$sum[hi][mask]$ 表示对于固定的 $hi$，低 9 位超集包含 $mask$ 的所有 $dp[hi][lo]$ 之和。

初始化 $dp$ 和 $sum$ 为 0。

处理 $a_j$：

1. $hi = a_j >> 9$, $lo = a_j \& 511$。
2. 查询 $s = 0$
   • 枚举所有 $hi'$ 满足 $hi' \& hi = hi$（即 $hi' \supseteq hi$）
   • 对于每个 $hi'$，$s += sum[hi'][lo]$
3. $f_j = 1 + s$
4. 答案加上 $f_j - 1$
5. 更新 $dp[hi][lo] += f_j$
6. 更新 $sum[hi][mask]$ 对所有 $mask \subseteq lo$：
   • 枚举 $mask$ 的所有子集 $sub$，$sum[hi][sub] += f_j$

枚举子集可以用 $sub = lo$; $sub = (sub-1) \& lo$ 循环。

复杂度

• 查询：枚举 $hi'$ 超集，最多 $2^{9}$ 个，对每个 $hi'$ 取 $sum[hi'][lo]$ 是 $O(1)$，总 $O(2^{9})$。
• 更新：枚举 $lo$ 的所有子集，最多 $2^{9}$ 个。 总复杂度 $O(n \cdot 2^{9})$，$2^{9}=512$，$n \approx 2\times 10^5$，可过。

最终答案

累计 $ans = \sum_{j} (f_j - 1)$，对 $10^9+7$ 取模。

注意 $f_j$ 和答案都需要取模。

边界情况

• $n=1$ 时答案为 0（因为需要长度至少为 2）
• 所有 $a_i$ 互不相同

算法步骤

1. 读入 $n$ 和 $a_i$。
2. 预处理 $B=9$，$S=512$。
3. 初始化 $dp[S][S]$ 和 $sum[S][S]$ 为 0。
4. $ans=0$。
5. 对 $j=1$ 到 $n$：
   • $hi = a_j >> 9$, $lo = a_j \& 511$
   • $s=0$
   • 枚举 $hi'$ 从 $hi$ 到 $S-1$，步长 1，但只取 $hi' \& hi = hi$ 的（即超集）
     • $s = (s + sum[hi'][lo]) \bmod MOD$
   • $f = (1 + s) \bmod MOD$
   • $ans = (ans + f - 1 + MOD) \bmod MOD$
   • $dp[hi][lo] = (dp[hi][lo] + f) \bmod MOD$
   • 枚举 $sub$ 为 $lo$ 的所有子集：
     • $sum[hi][sub] = (sum[hi][sub] + f) \bmod MOD$
6. 输出 $ans$。

---

这样即可在 $O(n \cdot 2^{9})$ 时间内解决问题，满足数据范围要求。