公式解説

https://atcoder.jp/contests/agc063/editorial/6740

の最後の参考に書いてあった、

• \(G(x) = F(x+1)\) を考える代わりに，高階微分係数の列 \(\bigl(F(1),F'(1),F''(1),\ldots\bigr)\) を考えても全く同じことになります．

について考えます。

• \(F_{v,1}(x) = \prod_{w\in\mathrm{ch}(v)}F_{w,4}(x)\)．
• \(F_{v,2}(x) = F_{v,1}(x^r)\)．
• \(F_{v,3}(x) = x^{a_v}F_{v,2}(x)\)．
• \(F_{v,4}(x) = F_{v,3}(x)+\dfrac{F_{v,3}(1)-F_{v,3}(x)}{1-x}\) .

をそれぞれ \(n\) 回微分したものを考えます

[1] \(F_{v,1}(x) = \prod_{w\in\mathrm{ch}(v)}F_{w,4}(x)\)

\(F^{(n)}_{v,1}(x)=n!\displaystyle\sum_{\sum m_{i}=n}\prod \dfrac{F^{(m_{i})}_{\mathrm{ch}(v,i),4}(x)}{m_{i}!}\)

これは

\(f(x)=\sum \dfrac{F^{(n)}(1)}{n!}x^{n}\)

とすると

\(f_{v,1}(x) = \prod_{w\in\mathrm{ch}(v)}f_{w,4}(x)\)

が成り立ちます。

[2]\(F_{v,2}(x) = F_{v,1}(x^r)\)

\(F^{(n)}_{v,2}(x) = \displaystyle\sum_{i=0}^{n} a_{i}F^{(i)}_{v,1}(x^r)x^{ir-n}\)

が成立する整数列 \((a_{0},a_{1},...,a_{n})\) が存在します。

\(n=0\) のときは \(a_{0}=1\) そうでないときは \(n-1\) 回微分した式をもう \(1\) 回微分することで求められます。

[3]\(F_{v,3}(x) = x^{a_v}F_{v,2}(x)\)

\(F^{(n)}_{v,3}(x) = \sum_{i=0}^{n}(\prod_{j=0}^{i-1}(a_{v}-j))x^{a_v-i}F^{(n-i)}_{v,2}(x)\)

[4]\(F_{v,4}(x) = F_{v,3}(x)+\dfrac{F_{v,3}(1)-F_{v,3}(x)}{1-x}\)

\(F\) が多項式のとき、任意の非負整数 \(n\) について以下が成り立ちます。

\(\dfrac{d^{n}\left(\dfrac{F(a)-F(x)}{a-x}\right)}{dx^{n}}|_{x=a}=\dfrac{F^{(n+1)}(a)}{n+1}\)

証明の一例としては、 \(F\) が多項式であることから、線形性より任意の非負整数 \(m\) について、 \(F(x)=x^{m}\) のときに上記が成り立つことを示せす方法があります。 これは \(m=0,1,..,n+1\) について成り立つことを示してから \(m\) に対する数学的帰納法で示すことができます。

以上より以下が成り立ちます。

\(F^{(n)}_{v,4}(1) = F^{(n)}_{v,3}(1)+\dfrac{F^{(n+1)}_{v,3}(1)}{n+1}\)

[5] まとめ

\(F_{v}^{(n)}(1)\) を \(n=0,1,...,N-1\) のまで持って動的計画法で計算すれば答えが求まることがわかりました。

計算量は公式解説と同じく \(O(N^{3})\) です。

pypy3 による実装例

https://atcoder.jp/contests/agc063/submissions/44099649