Just like the last time, the theme of this problem is the generating function.
Last time we wrote about technique-oriented topics, so this time we will tell you some intuition than technique.

The idea of generating function

Last time we wrote that a generating function is a function that has the sequence \(a_n\) as its coefficients. However, in this definition it is unclear how “the counted ‘objects’” relates to “generating function.”
So this time, we will describe from another viewpoint how two concepts, the counted ‘objects’ and the ‘families’ of them, closely relate to each other.

In combinatorics problems, two concepts always exist: the counted ‘objects’ (graphs, strings, sequences of operations, …) and the ‘families’ (or sets) of the objects. When the set has a certain good property, we may regard sets as generating functions.

For clarity, in the following editorial we will consistently use the following cases and typefaces for sequences, generating functions, and sets, described as follows:

• Sequence \(\to\) lowercase italic (\(a, b, c, \dots\))
• Generating function \(\to\) uppercase italic (\(A, B, C, \dots\))
• Set \(\to\) uppercase calligraphic (\(\mathcal{A}, \mathcal{B}, \mathcal{C}, \dots\) )

For example, let us first consider the following easy problem.

Takahashi decided to buy some number of bentos (a “bento” is a Japanese lunch box).
Cafeteria A sells \(a_i\) number of bentos for \(i\) yen (the currency in Japan) each. \((1 \leq i \leq 1000)\)
Cafeteria B sells \(b_j\) number of bentos for \(j\) yen each. \((1 \leq j \leq 1000)\)

(1) Takahashi decided to choose either Cafeteria A or B and buy a lunch box there. What are the possible combinations?
(2) Takahashi decided to two lunchboxes, from both of the cafeterias. What are the possible combinations? (3) Consider the generating function of “the number of combinations \(a_n\) for a total of \(n\) yen.” Express the generating function of (1) and (2) as generating functions.

For example, let us formulate the following case for instance: suppose that Cafeteria A sells two bentos, one for \(1\) yen and the other for \(2\) yen, and Cafeteria B sells two bentos, one for \(1\) en and the other for \(3\) yen.
Let us use a notation like \(1\) for a bentos from Cafeteria A, and \(1^\ast\) for Cafeteria B. Then, the set \(\mathcal{A}, \mathcal{B}\) of bentos of Cafeteria A and B are:

\[ \mathcal{A} = \lbrace 1, 2 \rbrace , \mathcal{B} = \lbrace 1^\ast , 3^\ast \rbrace. \]

Next, let us express the objects to count in (1) and (2) as sets, too.
The operation in (1) corresponds to an operation of merging two non-intersecting sets, and the operation in (2) corresponds to an operation of obtaining a combination by choosing one element from each of given sets.
In a broad sense, these operations can be regarded as a direct sum (a disjoint union) and a direct product of sets, so let us denote the operation of (1) by \(+\), and that of (2) by \(\times\).
In the example above, \(\mathcal{A} + \mathcal{B}\) and \(\mathcal{A} \times \mathcal{B}\) can be expressed as follows.

\[ \begin{aligned} \mathcal{A} + \mathcal{B} &= \lbrace 1,2,1^\ast, 3^\ast \rbrace \\ \mathcal{A} \times \mathcal{B} &= \lbrace 1, 2 \rbrace \times \lbrace 1^\ast , 3^\ast \rbrace \\ &= \lbrace (1,1^\ast), (1,3^\ast), (2,1^\ast), (2,3^\ast) \rbrace \end{aligned} \]

Next, let us replace them with the generating functions.

Let \(A(x)\) and \(B(x)\) be the generating functions of \(\mathcal{A}\) and \(\mathcal{B}\); then

\[ A(x) = \sum_i a_i x^i, B(x) = \sum_j b_j x^j.\]

The generating functions corresponding to (1) and (2) can be actually described with \(A(x)\) and \(B(x)\).
First, consider \(\mathcal{A} + \mathcal{B}\). If \(\mathcal{A}\) and \(\mathcal{B}\) are disjoint, then

• (the number of combinations in \(\mathcal{A}\) for a total of \(n\) yen) + (the number of combinations in \(\mathcal{B}\) for a total of \(n\) yen) = (the number of combinations in \(\mathcal{A} + \mathcal{B}\) for a total of \(n\) yen),

so, denoting by \(c_i\) the answer for a total of \(i\) yen, it holds that

\[ c_i = a_i + b_i.\]

By this equation, the generating function \(C(x)\) for (1) is obtained as

\[ \begin{aligned} C(x) &= \sum_{i} (a_i + b_i) x^i \\ &= A(x) + B(x). \end{aligned} \]

Next, \(\mathcal{A} \times \mathcal{B}\). Let \(d_i\) be the answer for the total of \(d_i\) yen, then

\[ d_k = \sum_{i + j = k} a_i b_j,\]

so it is derived that

\[ \begin{aligned} D(x) &= \sum_k \left(\sum_{i+j = k} a_i b_j\right) x^k \\ &= \sum_i a_i x^i \sum_j b_j x^j \\ &= A(x) \times B(x). \end{aligned} \]

In conclusion,

\[\mathcal{C} = \mathcal{A} + \mathcal{B} \iff C(x) = A(x) + B(x);\]

\[\mathcal{D} = \mathcal{A} \times \mathcal{B} \iff D(x) = A(x) \times B(x).\]

For example, for the case where \(\mathcal{A} = \lbrace 1, 2 \rbrace ,\mathcal{B} = \lbrace 1^\ast , 3^\ast \rbrace\),

\[ A(x) = x + x^2, B(x) = x + x^3;\]

\[C(x) = A(x) + B(x) = 2x + x^2 + x^3;\]

\[D(x) = A(x) \times B(x) = x^2 + x^3 + x^4 + x^5.\]

Comparing with the example above, it can be asserted that \(C(x)\) and \(D(x)\) are generating functions of \(\mathcal{A} + \mathcal{B}\) and \(\mathcal{A} \times \mathcal{B}\), respectively.

This example may have been too obvious that it is unclear why they are useful, so next we will introduce a bit more useful example.

Takahashi is going to climb a staircase, advancing one or two steps at once. For \(N = 0,1,\dots, n\), find the number of ways to climb a staircase of \(N\) steps.

Consider expressing “a way of climbing a staircase” a sequence. A sequence satisfying the condition consists of \(1\) or \(2\), and has a length at least \(0\). Therefore, the set of counted objects \(\mathcal{F}\) can be expressed as

\[\mathcal{F} = \lbrace \emptyset, (1), (2), (1, 1), (1, 2),(2,1), (2,2), \dots \rbrace.\]

Here, let us classify the elements of \(\mathcal{F}\) by whether he advanced \(1\) step or \(2\) steps in his first move. Then, by the recursive property of \(\mathcal{F}\), it can be described as

\[ \begin{aligned} &\mathcal{F} \\ &= \lbrace \emptyset \rbrace + \lbrace (1) \rbrace \times \lbrace \emptyset, (1), (2),\dots, \rbrace + \lbrace (2) \rbrace \times \lbrace \emptyset, (1), (2),\dots, \rbrace \\ &= \lbrace \emptyset \rbrace + \lbrace (1) \rbrace \times \mathcal{F} + \lbrace (2) \rbrace \times \mathcal{F}. \end{aligned} \]

Next, focusing on the “number of steps”, let us express \(\mathcal{F}\) as a generating function. If we replace the number of steps as the exponent part of \(x\), \(\emptyset\) can be replaced with \(x^0 = 1\), \((1)\) with \(x\), and \((2)\) with \(x^2\), so the generating function \(F(x)\) corresponding to \(\mathcal{F}\) is written as

\[ \begin{aligned} &F(x) = 1 + xF(x) + x^2 F(x) \\ &\to F(x) = \frac{1}{1 - x - x^2}. \end{aligned} \]

Indeed, the series expansion of \(F(x)\) is

\[F(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + \dots,\]

so it can be asserted that the desired sequence \((f_n)\) is equal to the Fibonacci sequence,

\[ (f_n) = 1, 1, 2, 3, 5, 8, 13, 21, \dots.\]

The two examples imply that a generating function is a minimum container that stores only necessary information (this time, like price or number of steps) of the object to be counted.
If the counted objects have certain good property, then the size of set of objects can be expressed by the elementary operations like additions and multiplications of generating functions, which turn out to be computable. One of the advantages of using generating functions is that such operations can be performed mechanically.

Having said that, you should not rely on generating functions too much. Note that in many cases, even if you obtained the generating function for the answer, obtaining the desired coefficient may require an advanced technique, and some expression is difficult to compute the coefficient.

Combinatorial “structure” and function composition

The previous chapter introduces only the following two operations: \(+\) and \(\times\). Now let us introduce a little more large “build block”.

A set of counted object is often on a combinatorial “structure”. (e.g. on a circumference, on a set, …) Such structures can be treated as a map from a set to another, \(\mathrm{C}(\mathcal{A})\).

It is worth noting that, if we know what kind of function \(\mathrm{C}\) is, then we can immediately illustrate the set of \(\mathrm{C}(\mathcal{A})\) by assigning \(\mathcal{A}\) to \(\mathrm{C}\).
So, no matter how complex structure the counted object has, once we know what kind of sets it is composed of, we may “decompose” it into some simple components so that the observation is drastically simplified.

As an easy example of “structure”, for some set \(\mathcal{A}\), consider a structure \(\mathrm{SEQ}(\mathcal{A})\) corresponding to “a sequence consisting of elements of \(\mathcal{A}\) with zero or more length.” A sequence of length \(i\) corresponds to \(\mathcal{A}^i\), so \(\mathrm{SEQ}(\mathcal{A})\) can be expressed as follows, where \(\mathcal{E}\) denotes the set of empty sequence:

\[\mathrm{SEQ}(\mathcal{A}) = \mathcal{E} + \mathcal{A} + \mathcal{A} \times \mathcal{A} + \mathcal{A} \times \mathcal{A} \times \mathcal{A} + \dots = \sum_{i=0}^\infty \mathcal{A}^i.\]

In the world of generating function, it is transformed to

\[S(x) = 1 + A(x) + A(x)^2 + \dots = \sum_{i=0}^\infty A(x) = \frac{1}{1 - A(x)}\]

by the formula of geometric series.

Let’s apply the structure \(\mathrm{SEQ}(\mathcal{A})\) to the problem. The previous example of Fibonacci sequence can be processed by assigning to \(\mathrm{SEQ}(\mathcal{A})\), too. “A way of climbing a staircase” can be regarded as a sequence of moves of length zero ore more, and the generating function of operation \(\mathcal{A}\) of “advancing one or two steps” is

\[A(x) = x + x^2,\]

so by assigning it to the formula above, the generating function \(F(x)\) of Fibonacci sequence can be immediately obtained as

\[F(x) = \frac{1}{1 - A(x)} = \frac{1}{1 - x - x^2}.\]

Let’s consider another meaningful example.

Takahashi is at \((0,0)\) of a 2D grid.
Takahashi will repeat the following move: choose two integers \(a\) and \(b\) such that \(0 \leq a, 0 \leq b, (a,b) \neq (0,0)\) and move to \((x,y) \to (x+a,y+b)\).
How many ways are there to arrive at \((N, N)\)?

This problem can be solved in a total of \(\mathrm{O}(N)\) time, which is not really obvious. This kind of combinatorics problem can be solved by mechanically using generating functions.

What “structure” Takahashi’s move have? Denoting by \(\mathcal{H}\) the vertical move, \(\mathcal{W}\) the horizontal move, and \(\mathcal{E}\) without moving to the direction, the structure can be expressed as

\[ \begin{aligned} &\mathcal{A} \\ &= (\mathcal{E} + \mathcal{H} + \mathcal{H}^2 + \dots) \times (\mathcal{E} + \mathcal{W} + \mathcal{W}^2 + \dots) - \mathcal{E} \\ &= \mathrm{SEQ}(\mathcal{H}) \times \mathrm{SEQ}(\mathcal{W}) - \mathcal{E}. \end{aligned} \]

• Here, \(-\) appears without a definition; it is informally defined as a operation satisfying \(\mathcal{C} = \mathcal{A} + \mathcal{B} \iff \mathcal{A} = \mathcal{C} - \mathcal{B}\).

As a generating function of two variables \(x\) and \(y\), the former of which correspond to the vertical move and the latter to the horizontal move, we obtain

\[ \begin{aligned} A(x, y) &= \left(\frac{1}{1 - x}\right) \left(\frac{1}{1 - y}\right) - 1 \\ &= \frac{1}{(1-x)(1-y)}-1 \end{aligned} \]

The structure of the desired solution is obviously the sequence of \(\mathcal{A}\), \(\mathrm{SEQ}(\mathcal{A})\), so the generating function \(F(x, y)\) turns out to be

\[ \begin{aligned} F(x, y) &= \frac{1}{1 - A(x,y)}\\ &= \frac{(1 - x)(1 - y)}{1 - 2x - 2y + 2xy} \end{aligned} \]

The answer can be found as the coefficient of \(x^N y^N\) in \(F(x,y)\). By the fact that

\[ \begin{aligned} &\lbrack x^a y^b \rbrack \frac{1}{1-2x-2y+2xy} \\ &= \sum_{i=0}^\infty (2xy-2x-2y)^i \\ &= \sum_{i=\max(a,b)}^{a+b} \binom{i}{a+b-i,i-a,i-b} 2^i (-1)^{b-a} \end{aligned} \]

the answer can be obtained in a total of \(\mathrm{O}(N)\) time.

As you can see, when the objects to be counted is composed of some “structures”, if we know the function of each of the “structures”, we can immediately obtain the generating function of the object to be counted by composing these functions.

The “structure” of multiset

By the way, if we go on the explanation, this article does not seem to work as a editorial of Problem H, so let us now consider the structure of multiset in order to solve Problem H.

We will prove the following fact.

Let the structure \(\mathrm{MULTISET}(\mathcal{A})\) be a multiset of elements of \(\mathcal{A}\). When

\[\mathcal{B} = \mathrm{MULTISET}(\mathcal{A}),\]

then the generating functions \(A(x), B(x)\) of \(\mathcal{A}, \mathcal{B}\) satisfies:

\[B(x) = \exp \left(\sum_{0 \lt k} \frac{A(x^k)}{k} \right).\]

In the terms of combinatorics world, it is interpreted like this.

There are many balls. There are \(a_w\) kinds of balls of weight \(a_w\). Two balls of the same kind cannot be distinguished.
Consider packing some balls into a bag. We want to find the number of ways \(b_w\) to pack the balls in a bag so that the sum of weight is \(w\).
Let \(A(x)\) and \(B(x)\) be the generating functions of \(a_w\) and \(b_w\). Then \(A(x)\) and \(B(x)\) have the following relationship:

\[B(x) = \exp \left(\sum_{0 \lt k} \frac{A(x^k)}{k} \right)\]

That is, \(\mathrm{MULTISET}\) is a “structure” that is used to express multi-choose.

There are several ways to derive the generating function \(B(x)\). First, we will introduce the approach of using the “structure” described above.

First, for simplicity, consider the case where all balls has a weight \(1\). Then, the desired generating function is that of multi-choose \(\ _n H_r\), where \(r\) is fixed.

Let \(\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_r\) be the structure corresponding to each of \(r\) kinds of balls. The desired structure has the form of “choose \(0\) or more balls from \(\mathcal{C}_1\), choose \(0\) or more balls from \(\mathcal{C}_2\), …” so it can be written as the following expression:

\[ \begin{aligned} &(\mathcal{E}+\mathcal{C}_1+\mathcal{C}_1^2 + \dots) \\ &\times (\mathcal{E}+\mathcal{C}_2+\mathcal{C}_2^2 + \dots) \\ &\vdots \\ &\times (\mathcal{E}+\mathcal{C}_r+\mathcal{C}_r^2 + \dots) \\ &= \prod_{i=1}^r \sum_{j=0}^\infty \mathcal{C}_i^j. \end{aligned} \]

When extracting only the information of number of balls to a generating function, \(\mathcal{C}_1,\dots,\mathcal{C}_r\) can all be replaced with \(x\), so in overall we have

\[ \frac{1}{(1-x)^r} = \sum_{i=0}^\infty \binom{r + i - 1}{r - 1} x^i.\]

(This indeed matches to the formula of multi-choose.)

Let us generalize it. Let \(\mathcal{D}_k\) be the structure of balls of weight \(k\), then by the discussion above,

\[\mathcal{B} = \prod_{0 \lt k} \left( \sum_{i=0}^\infty \mathcal{D}_k \right)^{a_k}.\]

When extracting only the information of number of balls to a generating function, \(\mathcal{D}_k\) can be replaced with \(x^k\), so we obtain

\[ B(x) = \prod_{0 \lt k} \left(\frac{1}{1-x^k}\right)^{a_k}.\]

All that left is technique. By applying a typical FPS (formal power series) technique called “\(\exp \log\) trick”,

\[ \begin{aligned} &B(x) \\ &= \exp \log B(x) \\ &= \exp \sum_{0 \lt k} -a_k \log (1 - x^k) \\ &= \exp \sum_{0 \lt k} a_k \sum_{0 \lt i} \frac{x^{ik}}{i}\\ &= \exp \sum_{0 \lt i} \frac{1}{i} \sum_{0 \lt k} a_k (x^i)^k\\ &= \exp \left(\sum_{0 \lt i} \frac{A(x^i)}{i} \right), \end{aligned} \]

so the desired answer is obtained.

There is another approach of using Pólya’s enumeration theorem. This is quite interesting, so we will introduce it as well.

First, we fix the number of balls to put in the bag to \(n\) and consider the generating function \(B_n(x)\) of the numbers of combinations in that case. Since \(B(x) = \sum_n B_n(x)\), what we want is the sum of \(B_n(x)\) over all \(n\).
By the Pólya’s theorem, the answer is the sum of numbers of fixed points of \(n!\) permutations, divided by \(n!\), so we will calculate that. Just like ABC226F, by grouping them by the multiset of lengths of cyclic permutations, the contribution when there is a cyclic permutation of length \(L\) can be obtained from the two values:

• the way of packing: \(A(x)^L\), since in the cyclic permutation of length \(L\), the \(L\) elements has exactly the same state
• cyclic permutation: \((L-1)!\)

so, by regarding a permutation \(p\) as a multiset that has \(F_i\) number of cyclic permutations of lengths \(L_i\) and expressing as \((L_1, F_1),(L_2, F_2),\dots\), the generating function \(E_s(x)\) of the number of fixed points corresponding to a multiset \(s\) is expressed as

\[ \begin{aligned} &B_s(x) \\ &= n! \cdot \prod_{(L,F) \in s} \frac{A(x^L)・((L-1)!)^F }{(L!)^F・F!} \\ &= n! \cdot \prod_{(L,F) \in s} \frac{(A(x)/L)^F}{F!}. \\ \end{aligned} \]

Let \(S_n\) be the set of multisets such that the sum of elements is \(n\). Then \(B_n(x)\) can be expressed by \(B_s(x)\) as

\[ \begin{aligned} &B_n(x) \\ &= \frac{1}{n!} \sum_{s \in S_n} B_s(x) \\ &= \frac{1}{n!} \sum_{s \in S_n} n! \cdot \prod_{(L,F) \in s} \frac{(A(x)/L)^F}{F!} \\ &= \sum_{s \in S_n} \prod_{(L,F) \in s} \frac{(A(x)/L)^F}{F!} \end{aligned} \]

where \(n\) is eliminated from the expression. (The initial \(\frac{1}{n!}\) corresponds to dividing by \(n!\) by the Pólya’s theorem.)
Therefore, the desired answer \(B(x)\) is the sum of \(\frac{B_s(x)}{n!}\) over all multisets \(s\), so

\[ \begin{aligned} &B(x) \\ &= \sum_s \prod_{(L,F) \in s} \frac{(A(x)/L)^F}{F!}, \\ \end{aligned} \]

and by grouping the expression above by \(L\), we obtain

\[ \begin{aligned} &B(x) \\ &= \prod_{0 \lt L} \left( 1 + \frac{A(x)}{L} +\frac{1}{2!} \left(\frac{A(x)}{L}\right)^2 + \frac{1}{3!} \left(\frac{A(x)}{L}\right)^3 + \dots \right) \\ &= \prod_{0 \lt L} \exp \left(\frac{A(x^L)}{L}\right) \\ &= \exp \left(\sum_{0 \lt L} \frac{A(x^L)}{L} \right).\\ \end{aligned} \]

Solution

Now that all preparation is done, we will explain how to solve the problem.

For simplicity, let us describe the problem in the terms of sets.

• Let \(\mathcal{F}\) be the set corresponding to a “non-empty bag”.
• Let \(\mathcal{G}\) be the set corresponding to a “gold blocks”.
• Let \(\mathcal{B}\) be the set corresponding to a “bag”.
• Let \(\mathcal{E}\) be the set corresponding to an “empty”.

Then, the constraints given in the problem statements can be expressed with \(\mathcal{B}, \mathcal{E}, \mathcal{F}, \mathcal{G}\) as

\[ \mathcal{F} = \mathcal{B} \times \left( \mathrm{MULTISET} (\mathcal{F} + \mathcal{G}) - \mathcal{E} \right).\]

Now, let us rephrase this as a generating function by eliminating all information but the weight.
Let \(F(x)\) be the generating function for the answer, and \(G(x) = \sum_{1 \leq i \leq K} x^{w_i}\) be the generating function for a gold block. (Here, \(F(x)\) satisfies \([x^0]F(x) = [x^1]F(x) = 0\).) Then, the set can be expressed as a generating function as follows.

\[\mathcal{B} \to x, \mathcal{E} \to 1, \mathcal{F} \to F(x), \mathcal{G} \to G(x)\]

Therefore, denoting \(H(x) = F(x) + G(x)\), the following relationship between \(F(x)\) and \(H(x)\) holds:

\[F(x) = x \left( \exp \left(\sum_{0 \lt k} \frac{H(x^k)}{k} \right) - 1\right)\]

by the derivation in the last chapter.

This is the end of the observation part; now here come the technique part. We want to somehow transform this into a form that can be computed fast.

For the problem like this, a typical approach is to differentiate the both hand sides. By differentiating the both hands sides of

\[F(x) = x \left( \exp \left(\sum_{0 \lt k} \frac{H(x^k)}{k} \right) - 1\right)\]

and multiplying \(x\), we obtain

\[xF'(x) = F(x) + (F(x) + x) \sum_{0 \lt k} x^{k} H'(x^k).\]

Here, defining

\[F^{\ast}(x) := \sum_k k f_k x^k,\]

we may simplify the expression above as

\[F^\ast(x) = F(x) + (F(x) + x) \sum_{0 \lt k} H^\ast(x^k).\]

For \(n \geq 2\), letting \(J(x) := \sum_{0 \lt k} H^\ast(x^k)\), and denoting by \(f\) and \(j\) the \(n\)-th coefficient of \(F(x)\) and \(J(x)\) respectively, we have

\[ \begin{aligned} n f_n &= f_n + j_{n-1} + \sum_{0 \lt k \lt n} f_k j_{n-k} \\ \to f_n &= \frac{1}{n - 1} \left(j_{n-1} + \sum_{0 \lt k \lt n} f_k j_{n-k}\right) \end{aligned} \]

(Here, we used \(f_0 = j_0 = 0\).) Also, each coefficient of \(j_n\) can be expressed as

\[ \begin{aligned} &j_n \\ &= \sum_{k | n} [x^n] H^\ast(x^k) \\ &= \sum_{k | n} [x^\frac{n}{k}] H^\ast(x) \\ &= \sum_{k|n} \frac{n}{k}(f_{\frac{n}{k}} + g_{\frac{n}{k}}) \\ &= \sum_{d|n} d (f_d + g_d), \\ \end{aligned} \]

so it can be computed if we know \(f_0, \dots, f_n\).
Therefore, with the two formula combined, the sequence \(f_n\) and \(j_n\) can be obtained in a total of \(\mathrm{O}(N \log^2 N)\) with divide-and-conquer FFT. Hence, the problem has been solved fast enough.

• Note that \(j_n\) depends on \(f_0, \dots, f_n\), so the same divide-and-conquer approach as ABC213H does not work, so you should be careful of when to do the transition. (If you have no idea: divide into cases depending on whether \(L = 0\) or not)

Note that this problem can even be solved in a total of \(\mathrm{O}(N \log N)\) time, but we will not mention the details here.

Advanced problem: counting unlabeled trees

In the homepage of OEIS, you can find the following sequence:

\[1,2,3,6,11,23,47,106,235\]

as an example in the search box. This is the first several terms of OEIS A000055, which is a sequence of numbers of unlabeled trees of \(N\) vertices.
Actually, the solution for this problem is based on the method of counting the unlabeled trees. Now, find the number of unlabeled trees of \(N\) vertices modulo \(998244353\) in a total of \(\mathrm{O}(N \log^2 N)\) time.