CF1327F 题解
$\text{Description}$
给定 $n,k,m$ 及 $m$ 个限制三元组形如 $(l_i,r_i,x_i)$。
计算满足下列条件且长度为 $n$ 的序列 $a$ 数量:
- $\forall i\in [1,n],a_i\in[0,2^k-1]$。
- $\forall i\in[1,m],\bigoplus\limits_{j=l_i}^{r_i}a_j=x_i$,其中 $\bigoplus$ 表示将这些数按位与。
$n,m\le 5\times 10^5,k\le 30$。
$\text{Solution}$
首先由于位运算对于每个二进制位都是独立的,所以我们可以按位考虑,那么问题转换为 01 问题。
考虑一个简单的 DP,令 $l(i)$ 表示只考虑前 $i$ 个数,最后一个 $0$ 可以填的最靠前的位置,这个东西实际上是所有限制三元组中满足 $x_j=0$ 且 $r_j\le i$ 的东西中最大的 $l_j$,因为如果不是最大的 $l_j$,就意味着有些限制三元组的区间内都是 $1$,与条件不符了。再令 $f(i,j)$ 表示前 $i$ 个数填好且最后一个 $0$ 的位置在 $j$ 的方案数,我们有以下转移:
- $j< l(i)$,此时不满足条件,则 $f(i,j)=0$。
- $j\in[l(i),i-1]$,此时只能填 $1$,故有 $f(i,j)=f(i-1,j)$。
- $j=i$,此时有转移:$f(i,i)=[\forall t\in [1,m],i\notin[l_t,r_t]]\sum\limits_{k=l(i-1)}^{i-1}f(i-1,k)$
复杂度太高,无法接受。但是我们发现第二种转移情况会使得 $\forall j\in[l(i),i-1]$ 都有 $f(i,j)=f(j,j)$,所以第三种转移的 sigma 又可以写成:$\sum\limits_{k=l(i-1)}^{i-1}f(k,k)$。
然后使用前缀和优化即可。
复杂度 $O(k(n+m))$。
$\text{Code}$
1 |
|