Inclusion-Exclusion Principle

Informally speaking, the object to be counted can be described as:

• (plant \(1\) or more seedlings to the \(1\)-st garden) and (plant \(1\) or more seedlings to the \(1\)-st garden) and (plant \(1\) or more seedlings to the \(1\)-st garden) …

However, it is very difficult to directly count them; a rough DP (Dynamic Programming) will cost a complexity of about \(\mathrm{O}(NABC) = \mathrm{O}(N^4)\).
On the other hand, changing the “plant” above to “not plant” makes it drastically easy; the answer is \(1\).
Like this problem, if “directly counting something is quite difficult, but substituting ‘and’ with ‘or’ or ‘\(A\)’ with ‘not \(A\)’ makes it simple,” then Inclusion-Exclusion Principle plays an active part.

Assign \(A_i :=\) (the number of ways to plant \(1\) or more seedlings to the \(i\)-th garden) to the formula of Inclusion-Exclusion Principle:

\[ \left|\bigcap_{i \in S} A_i \right| = \sum_{T \subseteq S} (-1)^{|T|} \left| \bigcap_{i \in T} \overline{A_i} \right|\]

then what we want to find can be informally expressed as

\[ \begin{aligned} &(\text{All the gardens have at least }1\text{ or more seedlings}) \\ &= (\text{At least }0\text{ specific gardens do not have a seedling}) \\ &- (\text{At least }1\text{ specific garden does not have a seedling}) \\ &+ (\text{At least }2\text{ specific gardens do not have a seedling}) \\ &- \dots \\ &= \sum_{i=0}^N (\text{At least }i\text{ specific gardens do not have a seedling}). \end{aligned} \]

The number of ways to plant seedlings so that (at least \(i\) specific gardens do not have a seedling) is

\[\binom{N}{i} \sum_{a=0}^{\min(A,N-i)} \binom{N-i}{a} \sum_{b=0}^{\min(B,N-i)} \binom{N-i}{b} \sum_{c=0}^{\min(C,N-i)} \binom{N-i}{c},\]

because

• the ways to choose the gardens that no seedlings are planted: \(\binom{N}{i}\) ways;
• the ways to plant apples: we can choose for each of \((N-i)\) gardens whether to plant \(0\) or \(1\) seedlings. There are \(\binom{N-i}{a}\) ways to plant \(a\) seedlings, so the number of ways is the sum over \(0 \leq a \leq \min(A,N-i)\);

and so on. Therefore, the answer is expressed as:

\[ \begin{aligned} &\sum_{i=0}^N (-1)^i \binom{N}{i} \sum_{a=0}^{\min(A,N-i)} \binom{N-i}{a} \sum_{b=0}^{\min(B,N-i)} \binom{N-i}{b} \sum_{a=0}^{\min(C,N-i)} \binom{N-i}{c} \\ &=\sum_{i=0}^N (-1)^{N-i} \binom{N}{i} \sum_{a=0}^{\min(A,i)} \binom{i}{a} \sum_{b=0}^{\min(B,i)} \binom{i}{b} \sum_{c=0}^{\min(C,i)} \binom{i}{c}. \end{aligned} \]

The equation above costs \(\mathrm{O}(N^2)\) time, which is a great improvement but still lead to TLE (Time Limit Exceeded), so we need an even better way.

Optimization using a grid

Are we stuck? Actually, we can reduce the complexity to \(\mathrm{O}(N)\) time by rephrasing in terms of grid.

With an aid of grid, when \(1!,2!, \dots,N!\) and \(\frac{1}{1!}, \frac{1}{2!}, \dots, \frac{1}{N!}\) are precomputed, based on

\[f_M(N) = \sum_{i=0}^{\min(N,M)} \binom{N}{i}\]

we can obtain

\[f_M(N + 1) = \sum_{i=0}^{\min(N+1,M)} \binom{N+1}{i}\]

in an \(\mathrm{O}(1)\) time, so that \(f_M(0), f_M(1), \dots, f_M(N)\) can be enumerated in a total of \(\mathrm{O}(N)\) time. We will explain how.

When \(N + 1 \leq M\), it is simple:

\[f_M(N + 1) = \sum_{i=0}^{N+1} \binom{N+1}{i} = 2^{N+1}\]

so

\[f_M(N + 1) = 2 \times f_M(N).\]

The problem is when \(N + 1 \gt M \iff N \ge M\); let’s use grid here.

Consider the following question: “You start walking from the lower-left point, moving up or right in one step. How many ways are there to reach one of the specified coordinate?” In the diagram below, what is the relation between

• the number of ways to move \(N\) steps to reach one of the red lattice points

and

• the number of ways to move \(N+1\) steps to reach one of the blue lattice points?

If you move one step up or right from one of the red point, you will end up with a blue point, with a small exception; so as the answer for the question above, we obtain the following equation:

\[ \begin{aligned} &(\text{The number of ways to reach one of the blue lattice points}) \\ &= 2 \times (\text{The number of ways to reach one of the red lattice points}) - (\text{The ways to reach the bottommost red lattice point and then move right}) \end{aligned} \]

Let us replace this with an expression using \(f_M(N)\), \(f_M(N+1)\), and binomial coefficients. Since \(\binom{a}{b}\) can be interpreted as “the number of ways when traveling from the lower-left point of the grid and move \(b\) steps to the right and \((a-b)\) to the up,”

• \(f_M(N)\) and \(f_M(N + 1)\) corresponds to the sum of the numbers of ways to reach one of the red and blue lattice points, respectively.
• The number of ways to reach the bottommost red lattice point is \(\binom{N}{M}\).

Therefore, replacing the equation above with binomial coefficient,we have obtained the relation

\[ f_M(N + 1) = 2 \times f_M(N) - \binom{N}{M}.\]

Hence, by defining binomial coefficients as \( N \lt M \iff \binom{N}{M} = 0\), for both cases we can express both cases with a single recurrence relation:

\[f_M(N + 1) = 2 \times f_M(N) - \binom{N}{M}\]

Together with the initial term

\[f_M(0) = 1,\]

we could enumerate \(f_M(0), f_M(1), \dots, f_M(N)\) in a total of \(\mathrm{O}(N)\) time.

By means of the transformation above, by inspecting in the increasing order of \(i\), the original expression’s

\[ \sum_{a=0}^{\min(A,i)} \binom{i}{a} ,\sum_{b=0}^{\min(B,i)} \binom{i}{b}, \sum_{c=0}^{\min(C,i)} \binom{i}{c}\]

can be transformed into

\[ \sum_{a=0}^{\min(A,i+1)} \binom{i+1}{a}, \sum_{b=0}^{\min(B,i+1)} \binom{i+1}{b}, \sum_{c=0}^{\min(C,i+1)} \binom{i+1}{c} \]

in an \(\mathrm{O}(1)\) time, thus we can compute entire sigma in a total of \(\mathrm{O}(N)\) time.

Since \(1!,2!, \dots,N!\) and \(\frac{1}{1!}, \frac{1}{2!}, \dots, \frac{1}{N!}\) can be enumerated in a total of \(\mathrm{O}(N + \log \mathrm{mod})\) or \(\mathrm{O}(N)\) time, the original problem has been solved in a total of \(\mathrm{O}(N + \log \mathrm{mod})\) or \(\mathrm{O}(N)\) time.

The following is a sample code in Python.

mod = 998244353
MAX = 5 * 10 ** 6 + 10

fac = [0] * (MAX + 1)
facinv = [0] * (MAX + 1)
fac[0] = 1
for i in range(1, MAX + 1):
  fac[i] = fac[i - 1] * i % mod
facinv[MAX] = pow(fac[MAX], mod - 2, mod)
for i in reversed(range(MAX)):
  facinv[i] = facinv[i + 1] * (i + 1) % mod

def binom(n, r):
  if n < 0 or r < 0 or n < r:
    return 0
  return fac[n] * facinv[r] % mod * facinv[n - r] % mod


N, A, B, C = map(int, input().split())
ans, a, b, c, sgn = 0, 1, 1, 1, 1 if N % 2 == 0 else -1
for i in range(N + 1):
  cur = binom(N, i) * a % mod * b % mod * c % mod
  ans += cur * sgn
  a = (a + a - binom(i, A)) % mod
  b = (b + b - binom(i, B)) % mod
  c = (c + c - binom(i, C)) % mod
  sgn = -sgn

print(ans % mod)

Exercises

Just like this problem, the technique of rephrasing combinatorics problems to vertices on grids is in fact typical in ARC and AGC; however introducing them as exercises here is a critical spoiler, so it’s very bad.
Instead, I will introduce some problems in which “diagonal segment on a grid” can be used as an unintended solution.

1

(1) (It’s maybe easy if you understand what is explained in the editorial)

Let

\[f(N, M) = \begin{cases} 0 & \min(N,M) \lt 0 \\ \displaystyle\sum_{i=0}^{\min(N,M)} \binom{N}{i} & \mathrm{otherwise}. \end{cases} \]

Suppose that \(1!,2!, \dots,N!\) and \(\frac{1}{1!}, \frac{1}{2!}, \dots\) are precomputed. Find \(f(N,M)\) from \(f(N + 1, M), f(N - 1, M), f(N, M + 1), f(N, M - 1)\) in an \(\mathrm{O}(1)\) time.

(2) (it’s worth 500 to 600 points if you figured out (1).)

Solve 天下一プログラマーコンテスト2014本戦 D : 高橋君 in a total of \(\mathrm{O}(N^{1.5})\) time, assuming \(N = 100000\). (Unfortunately, the problem is in Japanese.)

2

(It’s worth 600 points) Solve ABC234 F : Reordering for the case where only two kinds of alphabets appears in a total of \(\mathrm{O}(|S|)\) time.

3

(Its difficult) Educational Codeforces Round 78 F : Cards in a total of \(\mathrm{O}(N)\) time.