第一回日本最強プログラマー学生選手権決勝 F - Count Permutations Many Times

お題箱より。

難しめの（とはいえ上級者には比較的知名度が高い）テクニックを複数使いこなす必要がある問題です。公式解説では多項式の係数に対応させて解いていますが、そうではない方法で説明しようと思います。

解法

まずは1つのクエリだけを考える

まずはこの問題を、あるクエリ（区間） $\lbrack L, R\rbrack$ 1つだけについて解くことを考えましょう。

「 $p_{j} \ne A_{j}$ である」よりも「 $p_{j} = A_{j}$ である（違反状態である）」のほうが数えやすいので、包除原理を適用します。 $N$ 個の整数の集合を $S = \lbrace 0, ..., N-1\rbrace$ として、その部分集合 $s$ を考えます。 $s$ に含まれる整数が全て違反状態である（含まれない整数はどちらでもよい）ような場合の数を $C(s)$ とすると、求めたい答えは包除原理から

$\displaystyle \sum_{s\subset S}(-1)^{|s|}C(s)$

と計算することができます。ここで $|s|$ は $s$ の要素数を示します。

$C(s)$ の求め方を考えます。ある $s$ についてその要素を $x_{1}, ..., x_{|s|}$ と書きます。このときクエリで指定された区間 $A_{L}, ..., A_{R}$ に含まれている整数 $x$ の個数を $n(x)$ とすると、これは以下のように考えることができます。

まず $x_{1}, ..., x_{|s|}$ を置く場所を順番に決めてしまう。このとき整数 $x_{i}$ が違反する置き場所として取れるものは $n(x_{i})$ 通りあり、これらの場所は異なる整数間で重複することはない。
先に上記の $|s|$ 個を置き終わったら、残っている $N-|s|$ 個の整数を残っている $N-|s|$ 個の場所に自由に置く。

ということで、 $C(s)$ は以下のようになります。

$\displaystyle C(s) = \prod_{x \in s}n(x) \times (N-|s|)!$

これを全ての $s \subset S$ について個別に求めるのは当然できません。求めたい答えの計算において、サイズ $|s|$ が同じ部分集合には同じ係数 $(-1)^{|s|}(N-|s|)!$ が掛かることに注目すると、残った $\prod_{x \in s}n(x)$ をサイズが同じ集合ごとに合計したものが分かれば良さそうです。

ということで以下のDPを組みます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 整数 $0, ..., i-1$ までのうち $j$ 個を含むような集合全てについて、それぞれの集合を $s$ としたときの $\prod_{x \in s}n(x)$ の値を合計したもの。

これを最後まで計算したときの

$\displaystyle \sum_{j=0}^{N} \left( dp\lbrack N \rbrack\lbrack j \rbrack\times (-1)^{j}(N-j)!\right)$

の値が答えになります。

このDPにおける $dp\lbrack i \rbrack\lbrack j \rbrack$ からの遷移は次の2通りです。

整数 $i$ を集合の要素として採用する。 $n(i)$ を掛けて $dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack$ に足す。
整数 $i$ を集合の要素として採用しない。そのまま $dp\lbrack i+1 \rbrack\lbrack j \rbrack$ に足す。

これでクエリが1つの場合は $O(N^{2})$ のDPで解くことができました。このようにシンプルな遷移であることが後々効いてきます。

複数クエリではどうするか？

クエリとして区間が与えられるので、まず考えるのはセグメント木等です。ただこの問題の場合、2つの区間に対する計算結果（DPテーブル）をマージするのが難しいです。遷移の係数となっている $n(0), ..., n(N-1)$ が全部変わる可能性があるため、DPを最初から全部やりなおすことになります。

区間クエリの処理方法としてもう1つ重要テクニックがあります。Mo's Algorithm です。使える条件/やり方/計算量についてはリンク先を参照して欲しいのですが、これは

オフラインクエリである（いわゆるクエリ先読みができる）
区間を1要素分伸ばす/1要素分縮めて、答えを更新するという操作が妥当な計算時間でできる

という条件を満たす時に使えるテクニックです。

伸び縮みの計算量を $O(\alpha)$ として全体計算量は $O(\alpha(N+Q)\sqrt{N})$ 。 $N, Q$ が大きいと $O(\alpha)$ として許せる計算量は $O(1)$ や $O(\log N)$ くらいなのですが、今回は制約が小さいので $O(N)$ くらいならOKそうです。

要素を増やす/減らす処理を上手くやるには？

ある区間 $A_{L}, ..., A_{R}$ について、先ほどのDPの最終結果が求められているとします。そこから区間の要素を1つだけ増やす/減らすという処理を上手くやる方法はあるでしょうか？

このとき増えた/減った要素の値を $d$ とすると、DP遷移の係数となっている $n(0), ..., n(N-1)$ のうち変化するのは $n(d)$ だけです。そして先ほどのDPは、「戻すDP」というテクニックが適用できる形になっています。これは

今回の $0, ..., N-1$ の整数のように、DPの計算において見ていく順番が変わっても問題ない。
DPの遷移が単純で、 $dp\lbrack N \rbrack\lbrack\cdot\rbrack$ から $dp\lbrack N-1\rbrack\lbrack\cdot\rbrack$ を逆算することができる。