特殊な形式的冪級数 - かんプリンの学習記録

形式的冪級数を用いた珍しい(と思った)解き方がある問題集
(解けなかったやつも載せる)

厳密には形式的冪級数ではないもの(有理数の指数が出るもの)も載せてる．

ABC221 H

${\displaystyle[x^ky^N]\prod_{i=1}^{\infty}\frac{1-(xy^i)^{M+1}}{1-xy^i}}$

${1\leq M\leq N\leq 5000}$

解説

$f(x,y)=\prod_{i=1}^{\infty}\frac{1-(xy^i)^{M+1}}{1-xy^i}$ とする．
${\displaystyle f(xy,y)=\prod_{i=1}^{\infty}\frac{1-(xy^{i+1})^{M+1}}{1-xy^{i+1}}\\ \displaystyle =\prod_{i=2}^{\infty}\frac{1-(xy^i)^{M+1}}{1-xy^i}\\ \displaystyle =\frac{1-xy}{1-(xy)^{M+1}}f(x,y)}$
${[x^ky^{N-k}]f(1-x^{M+1})=[x^ky^N]f(1-xy)}$ なのでDP遷移がわかって解ける．

ABC222 H

${A(x)=x(1+3A(x)+A(x)^2)^2}$
${[x^N]A(x)}$

${1\leq N\leq 10^7}$

解説

${\dfrac{A(x)}{(1+3A(x)+A(x))^2}=x}$ であるので
${B(x)=\dfrac{x}{(1+3x+x^2)^2}}$ は ${A(x)}$ の逆関数となる．
ラグランジュの反転公式より
${\begin{eqnarray}[x^N]A(x)&=&\dfrac{1}{N}[x^{N-1}]\left(\dfrac{x}{B(x)}\right)^N\\ &=&\dfrac{1}{N}[x^{N-1}](1+3x+x^2)^{2N}\\ &=&\dfrac{1}{N}[x^{N-1}](1+3x+x^2)^{2N}\\ \displaystyle &=&\dfrac{1}{N}[x^{N-1}]\sum_{i=0}^{2N}\binom{2N}{i}x^{2N-i}(1+x)^{2i}\\ \displaystyle &=&\dfrac{1}{N}[x^{N-1}]\sum_{i=0}^{2N}\binom{2N}{i}x^{2N-i}\sum_{j=0}^{2i}\binom{2i}{j}x^j\\ \displaystyle &=&\dfrac{1}{N}\sum_{i=N+1}^{2N}\binom{2N}{i}\binom{2i}{i-N-1}\end{eqnarray}}$
したがって ${O(N)}$ で解ける．

ARC107 D

$[x^Ny^K]\prod_{i=0}^{\infty}\frac{1}{1-xy^{2^{-i}}}$

${1\leq K\leq N\leq 3000}$

解説

${[x^Ny^K]f(1-xy)=[x^Ny^{2K}]f}$ なのでDP遷移がわかって解ける．

UTPC2020 D

$[x^K]\sum_{i=1}^{N}\prod_{j=i}^{N}(1+M_j x)$

${1\leq K\leq N\leq 10^5}$
${1\leq M_i\leq 10^8}$

解説

$P(l,r)=\prod_{j=l}^{r-1}(1+M_j x), Q(l,r)=\sum_{i=l}^{r-1}\prod_{j=i}^{r-1}(1+M_j x)$ とする．
${P(l,r)=P(l,m)P(m,r)}$
${Q(l,r)=Q(l,m)P(m,r)+Q(m,r)}$
であるのでこれらの ${P,Q}$ を二分木のようにマージしていくことで ${O(N\log{N}\log{K})}$ で解ける．

yukicoder 0940

${\displaystyle[x^Xy^Yz^Z]\sum_{i=0}^{\infty}\left(\frac{1}{(1-x)(1-y)(1-z)}-1\right)^i}$

${0\leq X,Y,Z\leq 10^6}$

解説

${M=X+Y+Z}$ とすると，
${\displaystyle[x^Xy^Yz^Z]\sum_{i=0}^{\infty}\left(\frac{1}{(1-x)(1-y)(1-z)}-1\right)^i\\ \displaystyle=[x^Xy^Yz^Z]\sum_{i=0}^{M}\left(\frac{1}{(1-x)(1-y)(1-z)}-1\right)^i}$
となる． ${f=\frac{1}{(1-x)(1-y)(1-z)}}$ として，
${\displaystyle\sum_{i=0}^{M}(f-1)^i=\frac{(f-1)^{M+1}-1}{(f-1)-1}}$
となるので， ${f}$ に関する多項式と考えると ${f^i(0\leq i\leq M)}$ の係数は ${O(M)}$ で求められる．また， ${[x^Xy^Yz^Z]f^i}$ は二項係数の前計算により ${O(1)}$ で求められるので全体の計算量は ${O(M)}$

分割数

${\displaystyle[x^N]\prod_{i=1}^{\infty}\frac{1}{1-x^i}}$

${0\leq N\leq 500000}$

解説

オイラーの五角数定理より，
${\displaystyle\prod_{i=1}^{\infty}1-x^i=1+\sum_{i=1}^{\infty}(-1)^i\left(x^\frac{i(3i+1)}{2}+x^\frac{i(3i-1)}{2}\right)}$
となるので右辺 ${\bmod x^{N+1}}$ の逆数の ${x^{N}}$ の係数が答え．

分割数２

${\displaystyle[x^Ny^K]\prod_{i=0}^{\infty}\frac{1}{1-x^iy}}$

${1\leq K\leq N\leq 500000}$

解説

「 ${k}$ 個の非負整数に分割する方法の数」と「いくつかの ${k}$ 以下の正整数に分割する方法の数」は等しい*1 ので，
${\displaystyle[x^Ny^K]\prod_{i=0}^{\infty}\frac{1}{1-x^iy}=[x^N]\prod_{i=1}^{K}\frac{1}{1-x^i}}$ となり， ${O(N\log{N})}$
この式はDP遷移から求める方法やこの問題と同様に求める方法もある．

分割数３

${\displaystyle[x^Ky^N]\prod_{i=0}^{M}\frac{1}{1-x^iy}}$

${1\leq N,M,K\leq 500000}$

解説

これは ${K}$ を ${N}$ 個以下の「 ${M}$ 以下の非負整数」に分割する方法の数である。
これを用いると ${N}$ に関しての列挙を ${O(N\log{N})}$ で求めることができる．

分割数？

${\displaystyle[x^N]\prod_{i=1}^{\infty}\frac{1+x^{2i-1}}{1-x^{2i}}}$

${0\leq N\leq 500000}$

解説

${\displaystyle\prod_{i=1}^{\infty}\frac{1-x^{2i}}{1-x^{2i-1}}=\sum_{i=0}^{\infty}x^\frac{i(i+1)}{2}}$
となるので ${x\leftarrow -x}$ としたものの逆数の ${x^{N}}$ の係数が答え．

部分和

${\displaystyle[x^T]\prod_{i=1}^{N}(1+x^{s_i})}$

${1\leq N\leq 10^6}$
${1\leq T\leq 500000}$
${1\leq s_i\leq T}$

解説

以下 ${\bmod{x^{T+1}}}$ で考える．
${a_k}$ を「 ${s_i=k}$ となる ${i}$ の数」とする．
${\displaystyle\prod_{i=1}^{N}(1+x^{s_i})=\prod_{k=1}^{T}(1+x^k)^{a_k}}$ の対数をとる．
${\displaystyle\log\prod_{k=1}^{T}(1+x^k)^{a_k}\\ \displaystyle=\sum_{k=1}^{T}a_k\log(1+x^k)\\ \displaystyle=\sum_{k=1}^{T}\sum_{j=1}^{\infty}\frac{a_k(-1)^{j-1}}{j}x^{jk}\\ \displaystyle=\sum_{k=1}^{T}\sum_{j=1}^{\lfloor T/k\rfloor}\frac{a_k(-1)^{j-1}}{j}x^{jk}}$
これの ${\exp}$ をとればよい．

ABC235 G

${\displaystyle[x^{A}y^{B}z^{C}]\frac{((1+x)(1+y)(1+z)-1)^N}{(1-x)(1-y)(1-z)}}$

${1\leq N\leq 5×10^6}$
${0\leq A,B,C\leq N}$

解説

${\displaystyle[x^{A}y^{B}z^{C}]\frac{((1+x)(1+y)(1+z)-1)^N}{(1-x)(1-y)(1-z)}\\ =\displaystyle[x^{A}y^{B}z^{C}]\sum_{i=0}^{N}(-1)^{N-i}\binom{N}{i}\frac{(1+x)^i}{1-x}\frac{(1+y)^i}{1-y}\frac{(1+z)^i}{1-z}\\ =\displaystyle\sum_{i=0}^{N}(-1)^{N-i}\binom{N}{i}\sum_{a=0}^{\min(A,i)}\binom{i}{a}\sum_{b=0}^{\min(B,i)}\binom{i}{b}\sum_{c=0}^{\min(C,i)}\binom{i}{c}}$
${(0\leq i\leq N)}$ について， ${\displaystyle\sum_{a=0}^{\min(A,i)}\binom{i}{a}}$ の値を求める必要があるが，
${\displaystyle\sum_{a=0}^{\min(A,i+1)}\binom{i+1}{a}=2×\sum_{a=0}^{\min(A,i)}\binom{i}{a}-\binom{i}{A}}$ であるから ${i=0}$ から順に求めていけばよい．この式は二項係数の和をグリッド上の経路数に帰着させることで導くことができる．

ABC240 G

${\displaystyle[x^{X}y^{Y}z^{Z}]\left(x+x^{-1}+y+y^{-1}+z+z^{-1}\right)^N}$

${1\leq N\leq 10^7}$
${0\leq X,Y,Z\leq 10^7}$

解説

${\displaystyle[x^{X}y^{Y}z^{Z}]\left(x+x^{-1}+y+y^{-1}+z+z^{-1}\right)^N\\ = \displaystyle[x^{X}y^{Y}z^{Z}]\left( (x+y)\left(1+(xy)^{-1}\right)+\left(z+z^{-1}\right)\right)^N\\ = \displaystyle[x^{X}y^{Y}z^{Z}]\sum_{k=0}^{N}\binom{N}{k}(x+y)^k\left(1+(xy)^{-1}\right)^k\left(z+z^{-1}\right)^{N-k}\\}$
${x^Xy^Yz^Z}$ の係数を考えると
${= \displaystyle\sum_{k=0}^{N}\binom{N}{k}\binom{k}{\frac{k+X-Y}{2}}\binom{k}{\frac{k-X-Y}{2}}\binom{N-k}{\frac{N-k+Z}{2}}}$
となり，二項係数の前計算のもと ${O(N)}$ で求められる．
ただし，二項係数 ${\displaystyle\binom{n}{k}}$ は ${n,k}$ が ${0\leq k\leq n}$ を満たす整数でないとき ${0}$ と定義する．

ABC241 H

${\displaystyle[x^{M}]\prod_{i=1}^{N}\frac{1-(A_ix)^{B_i+1}}{1-A_ix}}$

${1\leq N\leq 16}$
${1\leq M\leq 10^{18}}$
${1\leq A_i < 998244353}$
${1\leq B_i \leq 10^{17}}$
${A_i \neq A_j}$

解説

分子は ${O(2^N)}$ 個の項からなるので，各項についてBostan-Mori法を適用すると ${O(2^NN^2\log{M})}$ または ${O(2^NN\log{N}\log{M})}$ で求められる．
適当な ${c_i}$ により ${\displaystyle\prod_{i=1}^{N}\frac{1}{1-A_ix}=\sum_{i=1}^{N}\frac{c_i}{1-A_ix}}$ と変形することができるので， ${O(2^NN\log{M})}$ でも求めることができる．

MojaCoder問(改)

${\displaystyle[x^{V}]\sum_{k=1}^{K}\prod_{i=1}^{N}(1+x^{v_i})^{k}}$

${1\leq N,V\leq 10^5}$
${1\leq K\leq 10^{18}}$
${1\leq v_i \leq V}$

解説

$f=\prod_{i=1}^{N}(1+x^{v_i})$ とする．
${f}$ は部分和を用い， ${O(N+V\log{V})}$ で求められる．
${\displaystyle[x^{V}]\sum_{k=1}^{K}f^k}$ を求めたいが， ${[x^0]f=1}$ であるので ${\displaystyle\sum_{k=1}^{K}f^k=\dfrac{f(1-f^K)}{1-f}}$ の分母・分子を適切に ${x}$ で割っておくことで ${O(V\log{V})}$ で求められる．

フィボナッチ数の総和

${\displaystyle[x^{M}]\frac{1}{(1-x-x^2)(1-x)^N}}$

${1\leq N\leq 2×10^5}$
${1\leq M\leq 10^{18}}$

解説

Bostan-Mori法を用いると ${O(N\log{N}\log{M})}$ かかり間に合わない．
${\displaystyle\frac{1}{(1-x-x^2)(1-x)^N}=\frac{a+bx}{1-x-x^2}+\frac{f(x)}{(1-x)^N}}$ となる ${a,b,f(x)}$ ( ${a,b}$ は定数 ${f(x)}$ は ${N-1}$ 次以下の多項式)を求めると， ${O(N+\log{M})}$ で求められる．

両辺 ${(1-x)^N}$ をかけて ${\displaystyle\frac{1}{1-x-x^2}=(a+bx)\frac{(1-x)^N}{1-x-x^2}+f(x)}$ の ${x^{N},x^{N+1}}$ の係数を比較することで ${a,b}$ が分かる( ${[x^{N}]f=[x^{N+1}]f=0}$ )． ${f(x)}$ も $f(x)=\frac{1-(a+bx)(1-x)^N}{1-x-x^2}$ となり求められる．

ECF Round 133 F

以下の問題が ${T}$ 個ある。各問題では ${N,M,K}$ が与えられる(それぞれの問題で独立)。

${\displaystyle\sum_{i=0}^{N}\binom{N}{i}a^{N-i}b^ii^K}$
ただし、 ${a=\lfloor\frac{M}{2}\rfloor ,b=\lceil\frac{M}{2}\rceil}$

${1\leq T\leq 5000}$
${1\leq N,M\leq 998244352}$
${1\leq K\leq 2000}$

解説

${\displaystyle\sum_{i=1}^{K}S(K,i)x^i=\left(\sum_{i=0}^{\infty}\frac{(-1)^i}{i!}x^i\right)\left(\sum_{i=0}^{\infty}\frac{i^K}{i!}x^i\right)}$ である。( ${S(n,k)}$ は第二種スターリング数)
$e^x\sum_{i=1}^{K}S(K,i)x^i=\sum_{i=0}^{\infty}\frac{i^K}{i!}x^i$
$e^{bx}\sum_{i=1}^{K}S(K,i)b^ix^i=\sum_{i=0}^{\infty}\frac{b^ii^K}{i!}x^i$
求める値は ${\displaystyle[x^{N}]e^{ax}\left(\sum_{i=0}^{\infty}\frac{b^ii^K}{i!}x^i\right)}$ であり、この式に入れると
${\displaystyle[x^{N}]e^{ax}e^{bx}\sum_{i=1}^{K}S(K,i)b^ix^i}$
${\displaystyle[x^{N}]e^{(a+b)x}\sum_{i=1}^{K}S(K,i)b^ix^i}$
これは ${O((\max{K})^2)}$ で第二種スターリング数の前計算のもとクエリあたり ${O(K)}$ で求められる。

解説

${K![x^K]e^{ix}=i^K}$ であるので、求める値は
${\displaystyle K![x^K]\sum_{i=0}^{N}\binom{N}{i}a^{N-i}b^ie^{ix}\\ \displaystyle K![x^K](a+be^x)^N}$
となり、前計算なしクエリあたり ${O(K\log{K})}$ で求められる。
${\displaystyle K![x^K](a+b+b(e^x-1) )^N\\ \displaystyle K![x^K]\sum_{i=0}^{N}\binom{N}{i}(a+b)^{N-i}b^i(e^x-1)^i}$
${e^x-1}$ の定数項は ${0}$ であるから ${0\leq i\leq \min(N,K)}$ で考えればよい。 ${[x^K](e^x-1)^i}$ を ${O((\max{K})^2)}$ で前計算することでクエリあたり ${O(K)}$ で求められる。

ABC281 H

${a_i = [x^i](1+x)^{A}\prod_{j=2}^{i-1}(1+a_j x)}$
このときの ${a_N}$

${1\leq N\leq 2×10^5}$
${1\leq A\leq 10^9}$

解説

オンライン畳み込みのような形になっているので分割統治を考える。
${f(x)=(1+x)^A, g_i(x)=\prod_{j=2}^{i-1}(1+a_j x)}$ とする。
${dc(l,r,h)}$ (ただし ${h=f(x)g_l(x)}$ )を ${\prod_{j=l}^{r-1}(1+a_j x)}$ を返す関数とすると、

dc(l,r,h):
    if r-l==1: 
        return (1+h_l x);
    m = (l+r)/2;
    g = dc(l,m,h);
    return g*dc(m,r,h*g)

と書けるが、最後の ${h*g}$ の部分で ${O(N\log{N})}$ かかる。
ここで、 ${dc(l,r,h)}$ では ${h}$ の ${l\dots r}$ 次の項しか必要ないので、全部で ${O(N\log^2{N})}$ で解ける。
${h}$ の ${l\dots r}$ 次の項しか必要ない理由：
${g=dc(l,m,h)}$ は ${m-l}$ 次であるため、 ${dc(m,r,h*g)}$ で使う ${h*g}$ の ${m\dots r}$ 次の項を求めるのには ${h}$ の ${l\dots r}$ 次の項しか必要ないということが帰納的に示される。

解説

https://atcoder.jp/contests/abc281/editorial/5385

*1:https://manabitimes.jp/math/888