>>549
そうだね、1-q^nは性質がよくてありがたい
たとえばq-二項係数なんかはbinom(n,r)_q = Π_{i=1}^{r} ((1-q^(n-i))/(1-q^i))と表せてlogを取ると

log binom(n,r)_q = Σ_{i=1}^{r} log (1-q^(n-i)) - Σ_{i=1}^{r} log (1-q^i)

なわけだけど、log (1-q^i) =　- Σ_{k=1} q^ik / k（ここで疎であることが効く）を利用し、
log binom(n,r)_qをN次まで求めるのならばO(NlogN)で求められる（調和級数）
binom(n,r)_q = exp(log binom(n,r)_q)もexp取る操作がNewton法でO(NlogN)でできて、最終的にはO(NlogN)