yukicoder No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│

いくつかの組合せ問題は多項式によって解くことができます。これがどういうことか、簡単な例を取り上げて説明します。サイコロを二個振ったとき目の和が k となる場合の数を求める問題を考えましょう。いきなりですが次の式を考えます。

\[ (x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6) \]

これを展開すると

\[ x^2 + 2x^3 + 3x^4 + 4x^5 + 5 x^6 + 6 x^7 + 5 x^8 + 4 x^9 + 3x^{10} + 2x^{11} + x^{12} \]

になります。さて $x^k$ の係数は何になっているでしょうか。実はサイコロの目の和が k になる場合の数と一致しています。なぜかを詳しく説明しませんが、このように多項式の係数を見ることでいくつかの問題は解くことができます。

さて、このことを踏まえて今回の問題を多項式で表すと

\begin{align}
[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} \left( \frac{1}{(1-x)(1-y)(1-z)} - 1 \right)^k
\end{align}

を計算する問題になります。ここで $[x^X y^Y z^Z] f(x,y,z)$ は多項式 $f(x,y,z)$ の $x^X y^Y z^Z$ の係数を表します。この式の組合せ的意味を考えるには、$1/(1-x)=1+x+x^2+\cdots$ と置き換えた方がいいでしょう。なお $1/(1-x)$ は一般には多項式ではなく形式的冪級数と呼ばれますが、ここでは多項式と呼びます。

上の式を計算するにあたって次のことを大切にします。

\[ [x^a y^b z^c] \left( \frac{1}{(1-x)(1-y)(1-z)} \right) ^n = {}_n \mathrm{H}_a \cdot {}_n
\mathrm{H}_b \cdot {}_n \mathrm{H}_c \]

これは $[x^k]1/(1-x)^n = {}_n \mathrm{H}_k$ であることと、$[x^a y^b] f(x)g(y)=([x^a] f(x))([y^b] g(y))$ であることから導けます。前者は式の組合せ的意味から分かることです。後者は明らかです。もちろん分解しなくても組合せ的に直接導けます。

ここから先は $f=1/(1-x)(1-y)(1-z)$ とします。これにより計算対象は $[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k$ に変わります。この式は等比数列の和の形をしているので、数学 B で習う等比数列の和の公式を使いまとめられます。

\[ [x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k = [x^X y^Y z^Z] \frac{(f-1)^{X+Y+Z+1} - 1}{(f-1) - 1} \]

右辺の分子ですが、二項定理で展開すると $\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}$ の形になります。$X+Y+Z+1$ 次式を一次式 $f - 2$ で割るというのは数学 II で習う筆算を使えば $O(X+Y+Z)$ で計算できます。最後に係数を取り出せば良くて、

\[ [x^X y^Y z^Z] (\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}) = \square [x^X y^Y z^Z] 1 + \square [x^X y^Y z^Z] f + \square [x^X y^Y z^Z] f^2 + \cdots + \square [x^X y^Y z^Z] f^{X+Y+Z} \]

です。これで解けました。和を $X+Y+Z$ まで取りましたが、無限に広げることもできますし、そちらの方が自然かもしれません。ただし僕が知る限りでは計算が大変になります。

https://yukicoder.me/problems/no/940

Some combinatorial problems can be solved by polynomial. To explain this, I prepare a simple example: Find the number of patterns such that the sum of two numbers on two dices equals k. To solve this, we consider the following polynomial

\[ (x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6). \]

By expansion, we obtain

\[ x^2 + 2x^3 + 3x^4 + 4x^5 + 5 x^6 + 6 x^7 + 5 x^8 + 4 x^9 + 3x^{10} + 2x^{11} + x^{12}. \]

What is the coefficient of $x^k$? Actually, it is equal to the number of ways that the sum of dices equals k. Although I won't explain the reason, we can understand the power of polynomials.

Let's try to represent this problem as polynomial. Then, the answer becomes

\begin{align}
[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} \left( \frac{1}{(1-x)(1-y)(1-z)} - 1 \right)^k.
\end{align}

In this article, $[x^X y^Y z^Z] f(x,y,z)$ denotes the coefficient of $x^X y^Y z^Z$ in $f(x,y,z)$. To understand the meaning of this expression, $1/(1-x)=1+x+x^2+\cdots$ might be useful. By the way, $1/(1-x)$ is called not a polynomial but a formal power series in general, but I call both of them a polynomial.

Formal power series - Wikipedia

The following relation is useful in this problem.

\[ [x^a y^b z^c] \left( \frac{1}{(1-x)(1-y)(1-z)} \right) ^n = {}_n \mathrm{H}_a \cdot {}_n
\mathrm{H}_b \cdot {}_n \mathrm{H}_c \]

Since the proof of this relation is easy, so I don't explain it here. Let $f=1/(1-x)(1-y)(1-z)$. Then the answer is changed into $[x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k$. This expression can be applied the sum of geometric sequence.

\[ [x^X y^Y z^Z] \sum_{k=0}^{X+Y+Z} (f-1)^k = [x^X y^Y z^Z] \frac{(f-1)^{X+Y+Z+1} - 1}{(f-1) - 1} \]

We apply the binomial theorem to the numerator of the right hand side, then it becomes $\square + \square f + \square f^2 + \cdots + \square f^{X+Y+Z+1}$. The division of a polynomial of degree $X+Y+Z+1$ and a polynomial of degree one can be computed in $O(X+Y+Z)$. Finally, we extract the coefficient from the result.