AOJ 2638 Hyperrectangle を FPS で考える

概要

onlinejudge.u-aizu.ac.jp

FPS で考えます。

(包除原理による解説は例えば次を参照ください)

drken1215.hatenablog.com

なぜ FPS か？

各 $x _ i$ の制約と、総和の制約を見て、FPS を直感しました。

実際、 $x _ i$ を $0$ 以上 $l _ i$ 以下の整数とすると、 $x_1 + \dots + x_d \leq s$ を満たす列 $(x _ i)$ の個数は次のように書けます。

\begin{align*} [x ^ s] \frac{1}{1 - x} \prod _ {i = 1} ^ d \frac{1 - x^{l_i + 1}}{1 - x} \end{align*}

$x_1 + \dots + x_d = s$ を満たす列 $(x _ i)$ を考えた後で、累積和を取れば良いです。

この式で $x_1 + \dots + x_d \leq s$ を満たす格子点の個数は求められました。

体積を近似する

問題は $x_i$ が実数であることです。FPS は離散値を扱いやすいので、点の間隔を小さくしていって、体積を近似することを考えます。

$k$ 個に分割するとして、 $\varepsilon = k^{-1}$ とおきます。各軸の選択は次のようになります。

\begin{align*} &\phantom{=} \sum_{e=0}^{l_i - 1} \left(x^e + x^{e + \varepsilon} + x^{e + 2\varepsilon} + \dots + x^{e + 1 - \varepsilon} \right) \\ &= \left(1 + x^{\varepsilon} + x^{2\varepsilon} + \dots + x^{1 - \varepsilon} \right) \sum_{e=0}^{l_i - 1} x^e \\ &= \frac{1 - x}{1 - x^\varepsilon} \cdot \frac{1 - x^{l_i}}{1 - x} = \frac{1 - x^{l_i}}{1 - x^\varepsilon} \end{align*}

指数部分に非整数があるので FPS から外れていますが、 $k$ 倍に引き伸ばせば正当になると思っています。

$k$ 個に分割したときの近似体積 $V_k$ は次のように書けます。累積和をとるときに $x^{i + n\varepsilon}$ も考慮する必要があることに注意します。

\begin{align*} V_k &= \varepsilon^d \times [x^s] \frac{1}{1 - x^{\varepsilon}} \prod_{i=1}^{d} \frac{1 - x^{l_i}}{1 - x^\varepsilon} \\ &= \varepsilon^d \times [x^s] \left(\frac{1}{1 - x^{\varepsilon}}\right)^{d+1} \prod_{i=1}^{d} \left(1 - x^{l_i}\right) \end{align*}

$f(x) = \prod_{i=1}^{d} (1 - x^{l_i})$ とします。負の二項定理から

\begin{align*} V_k = \varepsilon^d \sum_{i + j = s} \binom{i / \varepsilon + d}{d} \times f_j = \frac{1}{d!} \sum_{i+j = s} \frac{(i / \varepsilon + d)!}{(i / \varepsilon)!} \times \varepsilon^d \times f_j \end{align*}

ここで

\begin{align*} \frac{(i/\varepsilon + d)!}{(i/\varepsilon)!} \times \varepsilon^d &= \left(\frac{i}{\varepsilon} + d\right)\left(\frac{i}{\varepsilon} + d - 1\right) \dotsm \left(\frac{i}{\varepsilon} + 1\right) \times \varepsilon^d \\ &= (i + d\varepsilon) (i + (d-1) \varepsilon) \dotsm (i + \varepsilon) \longrightarrow i^d \ (\varepsilon \to 0) \end{align*}

よって求める値は次のようになります。

\begin{align*} d! V = \sum_{i+j=s} i^d \times f_j \end{align*}