AGC041-D
問題文
Editorial によると$N$が偶数のとき
$$
[q^{N-1}]\, \frac1{(1-q)[(1-q)(1-q^2)\dotsm(1-q^{N/2})]^2} \mod M
$$
$N$が奇数のとき
$$
[q^{N-1}]\, \frac1{(1-q)[(1-q)(1-q^2)\dotsm(1-q^{(N-1)/2})]^2(1-q^{(N+1)/2})} \mod M
$$
が解となる。
とても綺麗な母関数なので最初から形式的べき級数を用いた解法を考えたくなる。
以下その導出をする。行間はかなり広め。
導出
以下簡単のために$N$は偶数とする。
$M$で割った余りをとることについては考えない。
$A_N,\cdots,A_1$ を並べたヤング図形について考える。
□□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□
□□□□□□□
□□□□□□
上から $N/2-1$ 行の和が下から $N/2$ 行の和よりも小さくなるような $N$ 行高々 $N$ 列のヤング図形の個数が解である。
◆◆◆◆◆◆◆◆◆◆
◆◆◆◆◆◆◆◆◆
□□□□□□□□□
◇◇◇◇◇◇◇◇
◇◇◇◇◇◇◇
◇◇◇◇◇◇
ヤング図形を転置し、共役な分割を考える。
◆◆□◇◇◇
◆◆□◇◇◇
◆◆□◇◇◇
◆◆□◇◇◇
◆◆□◇◇◇
◆◆□◇◇◇
◆◆□◇◇
◆◆□◇
◆◆□
◆
図の ◆ の個数が ◇ の個数よりも真に小さい高々 $N$ 行 $N$ 列のヤング図形の個数は
$q$-ポッホハマー記号
$$
(a;q)_{n}:=\prod _{k=0}^{n-1}(1-aq^{k})
$$
を用いて
$$
\sum_{i < j} [q^ip^ja^N]\, \frac{aq^{N/2-1}p^{N/2}}{(a;q)_{N/2}(aq^{N/2-1};p)_{N/2+1}}
$$
と書ける。後はひたすら式変形していくと
\begin{align*}
&\sum_{i \le j} [q^ip^ja^{N-1}]\, \frac{q^{N/2}p^{N/2}}{(a;q)_{N/2}(aq^{N/2-1};p)_{N/2+1}}\\
=\,&\sum_{i} [q^ip^ia^{N-1}]\, \frac{q^{N/2}p^{N/2}}{(1-q)(a;q)_{N/2}(aq^{N/2-1};p)_{N/2+1}}\\
=\,&[a^{N-1}]\, \frac{1}{(1-q)(a;q)_{N/2}(aq^{N/2-1};q^{-1})_{N/2+1}}\\
=\,&[a^{N-1}]\, \frac{1}{(1-q)(a;q)_{N/2}(a;q)_{N/2}(1-aq^{-1})}\\
=\,&[a^{N-1}]\, \frac{1}{(1-a)(a;a)_{N/2}(a;a)_{N/2}}
\end{align*}
となり冒頭の式が得られる。
アルゴリズム
通常の動的計画法で $O(N^2)$ 時間で計算できる。
また、各因子の $\log$ をとってから和を取り、 $\exp$ で戻す $O(N\log N)$時間のアルゴリズムがある(参考)。
この問題の場合は動的な mod に対する高速フーリエ変換が必要であり、$N$ が大きくないと高速にならない。
ここでは五角数定理を用いた $O(N^{1.5})$ のアルゴリズムを紹介する。
分割数の母関数
$$
\prod_{n=1}^\infty \frac1{1-q^n}
$$
の分母を展開したものを明示的に与えるのが五角数定理である。
この分母は$N$次までに$O(\sqrt{N})$個しか非ゼロの項が存在しない。
そのため、愚直に漸化式に従って計算する方法で $O(N^{1.5})$ 時間で $N$ 項目までの計算ができる。
本問題の $N$ が偶数の場合を考えると
\begin{align*}
&[q^{N-1}]\, \frac1{(1-q)[(1-q)(1-q^2)\dotsm(1-q^{N/2})]^2}\\
=&[q^{N-1}]\, \frac{[(1-q^{N/2+1})\dotsm(1-q^{N-1})]^2}{(1-q)[(1-q)(1-q^2)\dotsm]^2}\\
=&[q^{N-1}]\, \frac{1-2q^{N/2+1}-\dotsb-2q^{N-1}}{(1-q)[(1-q)(1-q^2)\dotsm]^2}\\
\end{align*}
と式変形でき、五角数定理が適用できる形になる。
分子は都合よく積を展開する計算が省け、線形時間で計算できるようになった。
そのため全体の計算時間は $O(N^{1.5})$ である。
実装例