SRM763 1000pts ProductAndProduct

The answer is

\[ [x^M] \frac{1}{{}_N \mathrm{H}_M}\prod_{i=1}^{N} \left( C_i + (C_i+1)x + (C_i+2)x^2 + \cdots \right). \]

We already know

\[ 1+x+x^2+\cdots = \frac{1}{1-x}. \]

\begin{align}
x+2x^2 + 3x^3 + \cdots &= x \frac{d}{dx} (1+x+x^2+\cdots) \\
&= \frac{x}{(1-x)^2}
\end{align}

Hence,

\[ [x^M]\frac{1}{{}_N \mathrm{H}_M} \cdot \frac{1}{(1-x)^{2N}} \prod_{i=1}^{N} (C_i + (1-C_i)x). \]

The product of linear functions

\[ \prod_{i=1}^{N} (a_i + b_i x) \]

can be calculated in \(T(n)=2T(n/2)+O(n \log n)=O(n \log^2 n)\) by divide and conquer.

This is really unimpotant. We can define C and H as

\[ {}_n \mathrm{C}_r := [x^r] (1+x)^n, \]\[ {}_n \mathrm{H}_r := [x^r] (1-x)^{-n}. \]

In this definition, \({}_{n} \mathrm{C}_r\) and \({}_{n}\mathrm{H}_r\) is naturally defined for not only non-negative integers but also real values. Moreover, \({}_n \mathrm{H}_r = {}_{n+r-1} \mathrm{C}_{r}\) always holds even if n=r=0. In this calculation, we consider 1/x! as zero for all x<0 but we don't define x! for negative reals.

mint C2(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return F(n) * R(r) * R(n-r);
}
mint C(int n, int r) {
  if (r < 0) return 0;
  if (n >= 0) return F(n) * R(n-r) * R(r);
  mint v = F(-n+r-1) * R(-n-1) * R(r);
  return (r&1)==0 ? v : -v;
}
mint H(int n, int r) {
  return C(n+r-1, r);
}