yukicoder 3046 yukicoderの過去問

https://yukicoder.me/problems/no/3046

(First solution) M denote the maximum value of A. Then, the answer is

\[ [x^{M - 1}] (x^{M + K - 1} \bmod (x^{M}-x^{M - a_1}-\cdots - x^{M-a_N})). \]

https://yukicoder.me/submissions/334973

(Second solution) Consider the generating function. Then, the answer is

\[ [x^K] \sum_{i=0}^{\infty} (x^{a_1} + \cdots + x^{a_N})^i = [x^K] \frac{1}{1-x^{a_1}-\cdots - x^{a_N}}. \]

Inverses of formal power series can be computed in O(n log n) time by Newton's method.

https://yukicoder.me/submissions/334974

形式幂级数很好。我前年写过文章关于除法和逆元素。但是我删除了那个文章。然后我再写了新文章。虽然在以下中我不说牛顿法，而这是牛顿法。

Fast polynomial division

The quotient and the remainder of f(x) and g(x) are defined as the only q(x) and r(x) such that f(x)=q(x)g(x)+r(x) and deg r<deg g.
We have to calculate the product of two polynomials over Fp, but I won't mention it here.

Convert Division to Multiplication

The division can be achieved using the multiplication. For the polynomial $f(x)=a_0 + \cdots + a_n x^n$, we define $f^*(x)$ as follows:

\[f^{\ast}(x)=a_n+a_{n-1}x+\cdots+a_0x^n\]

Let q(x) and r(x) be the quotient and the remainder of f(x) and g(x), respectively. As mentioned earlier, f(x)=q(x)g(x)+r(x) holds. Apply $\ast$ to both sides, then

\[ f^{\ast}(x)=q^{\ast}(x)g^{\ast}(x)+x^{n-\deg r}r^{\ast}(x) \]

Since $n-\deg r \ge n-m+1$,

\[ f^{\ast}(x)\equiv q^{\ast}(x)g^{\ast}(x) \pmod{x^{n - m + 1}} \]

Multiply the inverse of $g^{\ast}$ to both sides, then

\[ f^{\ast}(x)(g^{\ast}(x))^{-1}\equiv q^{\ast}(x) \pmod{x^{n - m + 1}} \]

Since $\deg q \le n-m$, we finally obtain $q(x) \bmod x^{n-m+1}=q(x)$.
We used the inverse of g(x) here, but we haven't known the algorithm to find the inverse yet.
Next, we shall explain this algorithm.

The inverse of formal power series

Let $g(x)=a_0 + a_1x + \cdots + a_n x^n$. The inverse of g over mod x is $a_0^{-1}$. If the inverse of g over mod x^k is $t$, then the inverse of g over mod x^{2k} is $2t-t^2 g$. Thus, we can compute the inverses of g over mod x, mod x^2, mod x^4, mod x^8, ... recursively.

Proof: Let t be the inverse of g over mod x^k. Then, $gt=qx^k+1$. We then have,

\[(2t-t^2g)g= 2(qx^k+1)-(q^2x^{2k}+2qx^k+1)=-q^2x^{2k}+1.\]

Therefore, $2t-t^2g$ is the inverse of g over mod x^{2k}.

Let M(n) be the time complexity of the multiplication. Then, the time complexity to compute the inverse is $M(1)+M(2)+M(4)+\cdots + M(N)$. For example, if $M(n) = O(n \log n)$, it takes $O(n \log n)$.

Fast polynomial remainder

If we have $q$, we can find out $r$ because $r=f-qg$.

Applicaton

Multipoint evaluation

The problem statement is that given a polynomial $f$ of degree $N$, please find $f(X_0), \ldots, f(X_{N})$. We can solve this problem in $O(N \log^2 N)$ using the polynomial remainder. This problem is mentioned in the CLRS book.

Linear Recursion Relation

This problem can be reduced to the problem of finding the polynomial $x^n \bmod (x^m+a_{m - 1} x^{m - 1} + \cdots + a_0)$.

Reference

http://www.math.kobe-u.ac.jp/Asir/ca.pdf

This document is good for learning FFT. https://drive.google.com/file/d/1B9BIfATnI_qL6rYiE5hY9bh20SMVmHZ7/view