概要

負の添字を持つ対称な解配列と対称な遷移を持つ DP を行うにあたって、解配列の上半分だけを管理する方法とその注意点をご紹介します。

要するに DP 配列の母関数が $x \mapsto x ^ {-1}$ で不変な Laurent 多項式であるときです。

結論

$i \to i + j, |i - j|$ の形で遷移すること、数え上げの場合には $0$ 番目を $1 / 2$ 倍しておく（＆読み取るときには $2$ 倍する）ことに注意すれば OK です！

より詳しい説明

一旦スコープを数え上げ問題（可換環上の Laurent 多項式）に絞りましょう。

もとの Laurant 多項式 $f = \sum _ { -d \le i \le d } a _ i x ^ i$ を、$x ^ i + x ^ { -i }$ 型の多項式を用いて、$f = \sum _ { 0 \le i \le d } a' _ i \left ( x ^ i + x ^ { -i } \right )$ のように表すとよいです。

このとき係数同士の関係は次のようになります。特に $a _ 0$ と $a' _ 0$ の関係は、理解していても間違えやすいので注意してください。

$$ a'_i = \begin{cases} a _ i & i > 0 \\ \frac { a _ i } { 2 } & i = 0 \end{cases} $$

母関数の言葉を使わずに言うと次のようになります。

正の添え字はそのまま管理
負の添え字は管理しない
$0$ 番目は真の値の $1/2$ 倍を管理

積

$\left ( x ^ i + x ^ { -i } \right ) \left ( x ^ j + x ^ { -j } \right ) = \left ( x ^ { i + j } + x ^ { -i - j } \right ) + \left ( x ^ { i - j } + x ^ { -i + j } \right )$ であることに注意すると次のように計算できます。

fn mul(a: &[i64], b: &[i64]) -> Vec<i64> {
    if a.is_empty() || b.is_empty() {
        return Vec::new();
    }
    let mut c = vec![0; a.len() + b.len() - 1];
    for (i, &x) in a.iter().enumerate() {
        for (j, &y) in b.iter().enumerate() {
            c[i + j] += x * y;
            c[i.abs_diff(j)] += x * y;
        }
    }
    c
}

もちろん reverse したり shift したりなど工夫すれば FFT を利用して高速化することもできると思います。

よくある遷移だと $b$ の項数が $2$ とか $3$ とかだったりするので、そういうときには「右に遷移する」代わりに「左右に遷移する」みたいなイメージを持つと慣れやすいかもです。

truncate に関する注意

多項式や形式的べき級数の場合は $x _ i x _ j = x _ { i + j }$ のように高い次数同士の積は次数が高くなるので適宜 truncate する（mod $x ^ d$ で考える）ことが多いと思いますが、今回の場合は $x ^ { i - j } + x ^ { -i + j }$ という低次の項が出てくるので同じノリで truncate しないように気を付けましょう。（まあもとの Laurent 多項式の時点で当然ダメなんですけど。）