ARC110D nonFPS

Solution of ARC110D without formal power series

When Bi is less than Ai, the binomial coefficient is zero
So there is no need to consider cases where Bi is small.
$B_{i} = A_{i} + D_{i}$ . $D_{i} \geq 0$
$S := \sum A_{i}$ and the rest as [$ R:= M - S
$\sum D_{i} \leq R$ .
It takes the form of “distribute R (or less) balls in N frames.”
Consider distributing just K balls in 2 frames for simplicity
(0, K), (1, K-1), … , (K, 0), there is a way to distribute
The solution X2 we want is $X_{2} = \sum_{i = 0}^{K} (A _{1} A _{1} + i) (A _{2} A _{2} + K - i)$
There is a way to implement this naively and obtain it for some values and predict the answer formula from them (I did so), but in this page, I will do it by transforming the formula.
From the symmetry of the binomial coefficients $(A _{1} A _{1} + i) = (i A _{1} + i)$
$X_{2} = \sum_{i = 0}^{K} (i A _{1} + i) (K - i A _{2} + K - i)$
- nested combination : number of ways to select k out of n, allowing for duplication
- $H_{k}^{n} = (k n + k - 1)$
Write in the form of duplicate combinations:.
- $X_{2} = \sum_{i = 0}^{K} H_{i}^{A_{1} + 1} H_{K - i}^{A_{2} + 1}$
Duplicate combinations of A1+1 to i and A2+1 to K-i contents of sigma to choose from
Adding up for all possible i’s results in K duplicate combinations to choose from A1+A2+2.
- $X_{2} = H_{K}^{A_{1} + A_{2} + 2}$
Return to binomial coefficient form
- $X_{2} = (K A _{1} + A _{2} + K + 1)$
So far, the answer for distributing exactly K with N=2 can be expressed in terms of a single binomial coefficient
Next, consider N over 3.
- Rename variable K to i
  - $X_{2} = (i A _{1} + A _{2} + i + 1)$
- At this point, X at N=3 becomes
  - $X_{3} = \sum_{i} (i A _{1} + A _{2} + i + 1) (K - i A _{3} + K - i)$
- This is just A1 becoming A1+A2+1, so the argument above can be used as is.
  - $X_{3} = (K A _{1} + A _{2} + 1 + A _{3} + K + 1) = (K A _{1} + A _{2} + A _{3} + K + 3 - 1)$
At general N:.
- $X_{N} = (K S + K + N - 1)$
- This was just the solution when they were handing out K pieces.
- The answer X that the problem is asking for is the sum of everything below R
  - $X = \sum_{K = 0}^{R} (K S + K + N - 1)$
- Field hockey stick identity :
- $\sum_{i = 0}^{k} (i n + i) = (k n + k + 1)$
Field hockey stick identity to find the sum
- $X = \sum_{K = 0}^{R} (K S + K + N - 1) = \sum_{K = 0}^{R} (K S + N - 1 + K) = (R S + N - 1 + R + 1) = (R S + N + R)$
From the symmetry of the binomial coefficients
- $X = (R S + N + R) = (S + N S + N + R)$
$R := M - S$ , so
- $X = (S + N S + N + R) = (S + N N + M)$
Now the values to be sought are combined into a single binomial coefficient.
N+M will be about 10^9, but S+N will not be 10^7, so if properly implemented, it will be in time. - Binomial coefficient for huge n

This page is auto-translated from [/nishio/ARC110D nonFPS](https://scrapbox.io/nishio/ARC110D nonFPS) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.

🪴 Quartz 4.0

ARC110D nonFPS

Graph View

Backlinks