This problem features the algorithmic theme called Power Projection. Although we did not featured in FPS 24: 24 Problems on Formal Power Series, this technique was applicable to many high-difficulty combinatorics problems in 2025 (especially in AGCs (AtCoder Grand Contests), sponsored contests, and Universal Cup). If you want to be ready for high-level problems, do master it.

Power Projection

This chapter originates from the editorial of ABC387-G with edits.

We will introduce a problem called Power Projection, which is formulated as follows:

Power Projection

You are given polynomials \(f(x)\) and \(g(x)\) of degree \(n\). Let

\[h_i = \lbrack x^n \rbrack f(x)^i g(x).\]

Enumerate \(h_0, h_1, \dots, h_n\).

Power Projection has been found solvable in \(\mathrm{O}(n \log^2 n)\) by noshi91 in 2024. (Original article (Japanese). Translator’s note: see also this CodeForces article.) First, we consider the case where \(\lbrack x^0 \rbrack f(x) \neq 0\). Let \(\lbrack x^0 \rbrack f(x) = c\), then

\[\lbrack x^k \rbrack f(x)^i g(x) = \sum_{j = 0}^i \binom{i}{j} c^j \lbrack x^k \rbrack (f(x)-c)^{i-j} g(x)\]

so the answers can be found from the answers for \(f(x) \gets f(x)-c\) using convolution. Thus, we assume that \(\lbrack x^0 \rbrack f(x) = 0\).

If we represent the sought answer as a two-variable FPS, it is sufficient to find the following value up to the \(n\)-th degree polynomial of \(y\):

\[[x^n] \sum_{i=0}^\infty y^i f(x)^i g(x) = \lbrack x^n \rbrack \frac{g(x)}{1 - y f(x)}.\]

Now we will apply Bostan-Mori algorithm to this expression. (For the details of Bostna-Mori algorithm, refer to ABC300-Ex editorial.) Every time we apply the algorithm, the degree of \(y\) doubles, while the degree of \(x\) halves. In other words, in the \(t\)-th iteration, \(x\) has a degree of \(\lfloor n/2^t \rfloor\), and \(y\) has \(2^t\). Thus, the polynomial multiplication in each iteration costs \(\mathrm{O}(n \log n)\). Since \(\mathrm{O}(\log n)\) iterations are required, the overall complexity is \(\mathrm{O}(n \log^2 n)\).

The implementation of this algorithm is as follows.

• We use the FPS library in Nyaan’s Library. pre(n) is the function that extracts the first \(n\) terms of a value of fps type. If you do not understand the other part, see also the library.
• Note that we do not apply a constant-factor optimization for explanation, so this implementation is slow.

// Enumerates [x^n] f(x)^i g(x) for i=0,1,...,n
// For simplicty, assume [x^0] f = 0
template <typename mint>
FormalPowerSeries<mint> power_projection(FormalPowerSeries<mint> f,
                                         FormalPowerSeries<mint> g) {
  using fps = FormalPowerSeries<mint>;
  assert(f.size() == g.size());
  int n = f.size() - 1, k = 1;
  vector<fps> P(n + 1, fps(k + 1));
  vector<fps> Q(n + 1, fps(k + 1));
  Q[0][0] = 1;
  for (int i = 0; i <= n; i++) P[i][0] = g[i];
  for (int i = 0; i <= n; i++) Q[i][1] = -f[i];
  while (n) {
    auto R = Q;
    for (int i = 1; i <= n; i += 2) R[i] = -R[i];
    auto S = multiply2d(P, R);
    auto T = multiply2d(Q, R);
    vector<fps> U(n / 2 + 1, fps(k * 2 + 1));
    vector<fps> V(n / 2 + 1, fps(k * 2 + 1));
    for (int i = 0; i <= n / 2; i++) U[i] = S[i * 2 + n % 2], V[i] = T[i * 2];
    P = U, Q = V;
    n /= 2, k *= 2;
  }
  return (P[0] * Q[0].inv()).pre(f.size());
}

Solution

First, define \(f_n\) and \(g_n\) as follows:

• \(f_n :=\) (probability that when a person performs the operation \(n\) times, the piece does not reach the goal),
• \(f_n :=\) (probability that the piece reaches the goal by performing exactly \(n\) operations).

Obviously, \(g_n = f_{n-1} - f_n\) \((n \geq 1)\), and \(f_n = 0\) for \(n \geq N\). Thus, it is sufficient to compute \(f_0, f_1, \dots, f_{N-1}\).

Let \(D(x)\) be the generating function of the probability that one dice roll advances the piece by \(n\) squares. Namely,

\[D(x) = \frac{1}{M} \sum_{i=1}^M x^{A_i}.\]

Then the probability that the piece is at cell \(k\) after \(n\) dice rolls is represented as \([x^k] D^n\). Thus, we can represent as

\[ \begin{aligned} f_n &= \sum_{k=0}^{N-1} [x^k] D^n \\ &=[x^{N-1}] (1+x+\dots + x^{N-1}) D^n. \end{aligned} \]

Since the expression above is in the form of \([x^{\text{const.}}] F^n G\), the Power Projection algorithm is directly applicable. That is, \(f_0, f_1, \dots\), and \(f_{n-1}\) can be enumerated in \(\mathrm{O}(N \log^2 N)\) time.

Now that we have computed \(f_n\) and \(g_n\), let us find the answers. The probability that person \(i\) reaches the goal by the \(k\)-th move is

\[g_k f_{k}^{i-1} f_{k-1}^{L-i}.\]

The answer for person \(i\) is the sum of this value over \(k=1,2,\dots,N\).
For \(i=L\), we may naively sum them up, so assume \(1 \leq i \lt L\). If \(f_{k-1} = 0\), the above probability evaluates to \(0\) and ignorable, so assume \(f_{k-1} \neq 0\). Then the expression can be deformed as

\[ \begin{aligned} &g_k f_{k-1}^{L-1} \left(\frac{f_{k}}{f_{k-1}}\right)^{i-1} \\ &= [x^{i-1}] \frac{g_k f_{k-1}^{L-1} }{1 - \frac{f_{k}}{f_{k-1}} x}. \end{aligned} \]

The answer for person \(i\) is the sum of the value above over \(k=1,2,\dots,N\), which is:

\[\sum_{1 \leq k \leq N, f_{k-1} \neq 0} [x^{i-1}] \frac{g_k f_{k-1}^{L-1} }{1 - \frac{f_{k}}{f_{k-1}} x} = [x^{i-1}] \sum_{1 \leq k \leq N, f_{k-1} \neq 0} \frac{g_k f_{k-1}^{L-1} }{1 - \frac{f_{k}}{f_{k-1}} x}.\]

Hence, it is sufficient to find the coefficients of degrees between \(0\) and \((L-2)\) of:

\[\sum_{1 \leq k \leq N, f_{k-1} \neq 0} \frac{g_k f_{k-1}^{L-1} }{1 - \frac{f_{k}}{f_{k-1}} x}.\]

To compute this, apply the so-called “merge technique of FPS,” in which we compute the sum of the fractions in the manner of segment trees, to find the numerator and denominator of the sum in a total of \(\mathrm{O}(N \log^2 N)\). Then, spend \(\mathrm{O}(L \log L)\) time to find the inverse of the denominator polynomial (for more details on polynomial inverses, see also ABC260-Ex editorial), and multiply the result to the numerator.

Thus, the problem has been solved in a total of about \(\mathrm{O}(N \log^2 N + L \log L)\) time, which is fast enough.