Educational Codeforces Round 84 F. AND Segments

問題概要

整数 $n, k, m$ と、整数の組 $(l_{j}, r_{j}, x_{j})$ が $m$ 個与えられる。以下の条件を満たす長さ $n$ の整数列 $a_{1}, ..., a_{n}$ の個数を $\bmod 998244353$ で求めよ。

全ての要素は $0 \le a_{i} \lt 2^{k}$ を満たす。
整数の組で表現される以下の条件を個全て満たす。
- $a_{l_{j}}, ..., a_{r_{j}}$ のビットANDを取った値がちょうど $x_{j}$ となる。

制約

$1 \le n, m \le 5\times 10^{5}$
$1 \le k \le 30$
$1 \le l_{j} \le r_{j} \le n$
$0 \le x_{j} \lt 2^{k}$

解法

※解説・実装の都合上、 $a_{i}$ のインデックス $i=1, ..., n$ を1-indexedのまま扱うことにします。

この問題はビット桁ごとに独立に考えることができます。つまり一番下のビット桁を $0$ 桁目として、 $d=0, 1, ..., k-1$ についてそれぞれ「 $a_{1}, ..., a_{n}$ の $d$ 桁目の並びに相当する、 $0$ または $1$ からなる長さ $n$ の数列」の選び方を独立に求め、掛け合わせたものが答えになります。

具体的には $d$ ビット目を考える時には条件 $(l_{j}, r_{j}, x_{j})$ は以下のようになります。そして全てのビット桁においてこれらの条件が全て満たされることが問題の条件を満たす必要十分条件になります。

$x_{j}$ の $d$ ビット目が $1$ であれば、条件は「 $a_{l_{j}}, ..., a_{r_{j}}$ の $d$ ビット目が全て $1$ である」こと。
$x_{j}$ の $d$ ビット目が $0$ であれば、条件は「 $a_{l_{j}}, ..., a_{r_{j}}$ の $d$ ビット目の少なくとも1つが $0$ である」こと。

以降はある1つの桁についての数え上げパートを考え、 $a_{i}$ の該当桁の値（ $0$ または $1$ ）を単に $a_{i}$ と表記します。

まずは「区間内が全て $1$ 」タイプの条件に基づいて、各インデックス $i$ が「必ず $a_{i} = 1$ にならないといけない」かどうかを求めておきます。こちらのタイプに属する条件区間 $\lbrack l_{j}, r_{j}\rbrack$ 全ての和集合を取れば良いので、imos法を使うことで全てのインデックスについてまとめて計算することができます。

次は「区間内の少なくとも1つが $0$ 」タイプの条件を上手く扱いながら数え上げていきます。準備としてこちらのタイプに属する条件区間 $\lbrack l_{j}, r_{j}\rbrack$ を列挙し、右端 $r_{j}$ ごとに分類しておきます。

結論から言うと、次のようなDPを考えれば良いです。

$dp\lbrack i \rbrack =$ 要素の値を $a_{1}, ..., a_{i}$ まで決めてしまって、 $a_{i} = 0$ であって、「区間内は全て $1$ 」タイプの条件に違反せず、かつ「少なくとも1つが $0$ 」タイプの条件区間のうち右端が $r_{j} \le i$ であるものに違反していないような $a_{1}, ..., a_{i}$ の個数

ただし $0$ が1度も登場していないようなものは $dp\lbrack 0\rbrack$ として扱うことにします。

ちょっとややこしいですが、最後に登場した $0$ の位置で分類して数えているというところがキモです。この $dp\lbrack i \rbrack$ への遷移を考える時には、 $s \lt i$ である $s$ に対して、 $dp\lbrack s\rbrack$ として数えられている数列 $a_{1}, ..., a_{s}$ について「 $a_{s+1}$ から $a_{i-1}$ までを $1$ で埋めて、 $a_{i}$ を $0$ にする」と続けるような遷移をすることになります。

具体的な遷移計算を考えます。まず $i$ が先ほどの「必ず $a_{i} = 1$ にならないといけない」インデックスだった場合は必ず $dp\lbrack i \rbrack = 0$ です。

そうでない場合、遷移元として選べる $s$ は、 $a_{s+1}$ から $a_{i-1}$ までを $1$ で埋めても「区間内の少なくとも1つが $0$ 」タイプの区間を塞がないようなものです。つまり区間のうち $r_{j} \lt i$ であるものに対する $l_{j}$ の最大値を $L_{i}$ とすると、遷移元として条件違反にならないのは $L_{i} \le s \lt i$ の範囲です。

f:id:betrue12:20200325002212p:plain

このように、遷移元となるのはある区間における $dp\lbrack s \rbrack$ の和です。そのためDPテーブルを埋めながら同時に累積和も求めておくか、 $L_{i}$ が単調増加であることを利用してしゃくとり法のように $L_{i}$ からの区間和の値を管理することで効率的に計算できます。

$dp\lbrack N \rbrack$ まで埋め終わったら、 $L = \max_{j} l_{j}$ として $L \le s \le N$ であるような $dp\lbrack s \rbrack$ の合計が求めるべき場合の数になります。正しくは、 $dp\lbrack s \rbrack$ として数えられている数列 $a_{1}, ..., a_{s}$ について $a_{s+1}, ..., a_{N}$ を全て $1$ で埋めたものを数えていることになります。