题解

思路

零与非零尾部分离

值 $0$ 与任何数按位与都为零，所以每个零一定新建一个子序列，之后也永远不会再有元素接到它后面。于是

所有子数组中零的总贡献可在线维护：处理到位置 $r$ 时，若 $a_r=0$，则所有 $r$ 个以 $r$ 结尾的子数组都多一个零，所以这些后缀的零数总和增加 $r$。

非零尾列表只有 16 种状态

非零元素只有 $1,2,3$。对尾列表执行一次转移：把 $x$ 写到第一个满足按位与非零的位置；若没有则追加。

从空列表出发，对 $1,2,3$ 反复执行转移，闭包恰有 16 个状态：空状态以及 15 个非空状态，最长列表长度为 3。可以用 BFS 自动生成这 16 个状态及三种非零值的转移表；值 $0$ 对非零状态不产生变化。

维护 cnt[s]：当前右端点下，以状态 $s$ 结尾的后缀个数。加入 $a_r$ 时，把全部状态按转移表汇总到新状态，并加入只含 $a_r$ 的新后缀。此时非零子序列数贡献为

再加上所有当前后缀的零数总和，就得到所有以 $r$ 为右端点的 $f$ 之和；对 $r$ 累加即为答案。

做法

子任务 1：每个子数组重新模拟

枚举左右端点，并从头模拟该子数组的完整分解，复杂度 $O(n^3)$。

子任务 2：固定左端点增量扩展

固定左端点，右端点每右移一格，只对当前尾列表执行一次转移并立刻累加列表长度，复杂度 $O(n^2)$。

子任务 3：有限状态后缀动态规划

BFS 建立 16 状态自动机，逐右端点转移全部后缀状态计数，复杂度 $O(16n)$。

正确性证明

引理 1：零元素对 $f$ 的贡献彼此独立，每个零恰贡献一个永久子序列，且不改变非零尾列表的相对顺序和转移。

证明：零与所有末尾元素按位与均为零，因此它只能新建子序列；以后任何值与该零尾也不兼容，扫描时只会跳过它。

引理 2：忽略零后，所有可达尾列表恰位于 BFS 从空状态得到的 16 状态闭包中。

证明：初始为空；每读入一个非零值只会执行定义中的确定转移，而 BFS 对每个已知状态枚举了三个可能输入，故归纳可知实际状态都在闭包中。反之 BFS 中每条边都对应一次合法输入，所有生成状态均可达。

引理 3：处理完位置 $r$ 后，cnt[s] 恰等于所有以 $r$ 结尾且非零尾状态为 $s$ 的子数组个数。

证明：旧的每个后缀按 $a_r$ 的唯一转移进入新状态；只含 $a_r$ 的新后缀另行加入。两类后缀不重不漏。

定理：算法输出等于题目要求的双重求和。

证明：由引理 1，每个后缀的 $f$ 等于零数与非零状态长度之和；由引理 3，算法对固定右端点恰好汇总全部后缀。再对所有右端点累加，覆盖全部子数组且不重复。

复杂度

• 子任务 1：$O(n^3)$ 时间，$O(n)$ 空间。
• 子任务 2：$O(n^2)$ 时间，$O(n)$ 空间。
• 子任务 3：$O(16n)$ 时间，$O(16)$ 空间。