公式解説では、ラベルのついてるマスの数で場合分けしていましたが、このような場合わけをしなくても \(O(N^3)\) で解くことができます。

方針

公式解説の基本方針と同じようにラベル\(1,2,...,N^2\)それぞれについてそのラベルがついているマス \((x_1,y_1),(x_2,y_2),...,(x_k,y_k)\)を考え、これらのうち \(1\) つが始点で \(1\) つが終点であるような経路が数えられれば良いです。

公式解説の解法1のように始点と終点を全探索すると、各ラベルについての答えは以下の式で表されます。

\(\sum_{j=1}^{k}\sum_{i=1}^{k} \dbinom{x_j+y_j-x_i-y_i}{x_j-x_i}\)

この式は、任意の \(1\leq i \leq j\leq k\) について、\(x_i+y_i \leqq x_j+y_j\) が成り立っているとき、二項係数の性質を用いて以下のように変形できます。

\(\sum_{j=1}^{k}\sum_{i=1}^{j} \dbinom{x_j+y_j-x_i-y_i}{x_j-x_i}\)

\(=\) \(\sum_{j=1}^{k}\sum_{i=1}^{j}([T^{x_j-x_i}](1+T)^{x_j+y_j-x_i-y_i})\)

\(=\) \([T^0]\sum_{j=1}^{k}\frac{(1+T)^{x_j+y_j}}{T^{x_j}} \sum_{i=1}^{j}\frac{T^{x_i}}{(1+T)^{x_i+y_i}}\)

\(=\) \([T^N]\sum_{j=1}^{k}{(1+T)^{x_j+y_j}}{T^{N-x_j}} \sum_{i=1}^{j}\frac{T^{x_i}}{(1+T)^{x_i+y_i}}\)

また、形式的冪級数を用いて以下のような等式が成立します。

\(\frac{T^{x_i}}{(1+T)^{x_i+y_i}}=\sum_{n=0}^{\infty}(-1)^{n}T^{n+x_i}\dbinom{n+x_i+y_i-1}{x_i+y_i-1}\)

よって、以下のような手順で答えを導き出すことができます。

• 変数 \(ans\) と \(N\) 次の多項式 \(f(T)\) が存在して、始め、 \(ans=0,f(T)=0\) である。

• 「\( f(T)\leftarrow f(T)+ \frac{T^{x_j}}{(1+T)^{x_j+y_j}}\)と更新したあと、 \(ans\) に \([T^N](f(T){(1+T)^{x_j+y_j}}{T^{N-x_j}})\) を足す」 という操作を \(j=1,2,..,k\) の順に行う。

コンビネーションを事前に計算して \(O(1)\) で計算できるようにしておくことで、\(f(T)\) を更新するのに \(O(N)\) 、\(ans\) に加算するのに \(O(N)\) で計算できます。

この操作は全てのラベルを合わせて \(N^2\) 回行うため、計算量は \(O(N^3)\) です。

実装例 c++

実装例 pypy3

参考: AGCのネタバレあり