計算量 \(O(N\log(N))\) で解く方法です。

この解説はこの問題と非常によく似た問題が出たコンテストについて、当時議論された codeforces 上 のブログでの Um_nik 氏のコメント を参考としており、シンプルな英語で書かれているため英語が苦手な方でも理解しやすいと思いますが、日本語でも記述しておきます。

ボトルネックとなっている部分は、公式解説にもあるように、 \(\prod_{i=1}^{K}(1+B_{i}x)\) を計算するところです。

ただし、 \(B_{i}\) は \(A_{x_i}=-1\) である頂点が含まれている連結成分の頂点の数であることから、 \(\sum_{i=1}^{K}B_{i}\leq N\) であることに留意します。

ここで\(B_i=j\) であるような \(i\) の数を \(d_j\) とすると以下が成り立ちます。

• \(\prod_{i=1}^{K}(1+B_{i}x)=\prod_{j=1}^N(1+jx)^{d_j}\)
• \(\sum_{j=1}^{N}jd_{j}\leq N\)

まず、\((1+jx)^{d_{j}}=\sum_{i=0}^{d_{j}} \ _{d_{j}} C_{i}(jx)^{i}\) であることから、 \((1+jx)^{d_{j}}\) は \(O(d_{j})\) で計算できることから全体で \(O(N)\) で計算できます。

次に最終的に答えとなる多項式を \(ans=1\) と初期化して、\(j\)の降順に \(ans\leftarrow ans*(1+jx)^{d_{j}}\) と更新します。

ある \(j\) について更新のときにかかる計算量は、畳み込みを使うことで \(O((d_{j}+d_{j+1}+...d_{N})\log(N))\) であることがわかります。

ここで、\(\sum_{j=1}^{N}(\sum_{k=j}^{N}d_{k})=\sum_{j=1}^{N}jd_{j}\leq N\) であることから、この畳み込みにかかる計算量は \(O(N\log(N))\) となります。

よって、 \(ans\) を \(O(N\log(N))\) で計算できたため、この問題を \(O(N\log(N))\) で計算できます。

実装例 (c++ 8ms)