General Highway Inspection#12828

General Highway Inspection (Editorial)

Матвій Асландуков

Для зручності позначимо міста Doublein, Longdon та Longlongdon як перше, друге та третє місто відповідно. Також будемо вважати, що існує рівно доріг між першим та другим містом, доріг між другим та третім, та доріг між третім та першим (для цього у вхідних даних треба поміняти числа та місцями).

Розглянемо будь-який шлях, який починається та завершується в першому місті, та проходить через кожну з (a+b+c) доріг рівно один раз. Нехай у цьому шляху було рівно переходів від першого міста до другого, — від другого до третього, та — від третього до першого. Оскільки шлях проходив через кожну дорогу рівно один раз, то на ньому також було рівно (a-x) переходів від другого міста до першого, (b-y) — від третього до другого, та (c-z) — від першого до третього (див. рис. 1).

Оскільки наш шлях є циклом, то для будь-якого міста сумарна кількість виходів з нього дорівнює сумарній кількості входів до нього. А тому мають місце наступні рівності:

  1. x + (c - z) = (a - x) + z;

  2. y + (a - x) = (b - y) + x;

  3. z + (b - y) = (c - z) + y,

З першого та другого рівнянь отримуємо z = \frac{2x + c - a}{2}, y = \frac{2x + b - a}{2}. Таким чином, знаючи лише тільки , можна однозначно визначити кількість проходів по кожному типу доріг в обидві сторони.

Подивимось, як можна знайти кількість шляхів для заданих , , . Будемо вважати, що усі дороги одного типу еквівалентні між собою (в кінці потрібно буде помножити відповідь на a!\, b!\, c!, оскільки всі дороги все ж таки різні). Розглянемо усі моменти часу, коли ми знаходилися в першому місті, та повинні були перейти до наступного міста. Усього таких моментів було x + (c - z), серед яких рівно разів ми перейшли до другого міста. Тому кількість способів зафіксувати порядок переходів з першого міста до наступного — C_{x+c-z}^{x} = \frac{(x+c-z)!}{x! (c-z)!}. Аналогічно кількість способів зафіксувати порядок переходів з другого та третього міст дорівнює C_{y+a-x}^{y} та C_{z+b-y}^{z} відповідно. Загальну кількість шляхів для заданих , , можна підрахувати як w = f(a, b, c, x, y, z) = C_{x+c-z}^{x} \cdot C_{y+a-x}^{y} \cdot C_{z+b-y}^{z}. Кожен з способів буде відповідати певній послідовності переходів, що починається та закінчується в першому місті. Але деякі з них не будуть відвідувати усі дороги, а саме певну кількість доріг між другим та третім містом. Це можливо у випадку, коли є хоча б один перехід від другого міста до третього, та від третього міста до другого, тобто 1 \leq y, b - y. У такому випадку від необхідно відняти f(a, b - 2, c, x, y - 1, z).

Таким чином, остаточна відповідь на задачу дорівнює a!\,b!\,c! \sum\limits_{x=0}^a (f(a, b, c, x, y, z) - f(a, b - 2, c, x, y - 1, z)), де y = \frac{2x + b - a}{2}, z = \frac{2x + c - a}{2}, а f(a, b, c, x, y, z) вважається рівним нулю у випадку, коли хоча б одне з чисел , не є цілим, або ж не виконується обмеження 0 \leq y \leq b, 0 \leq z \leq c.

Для швидкого підрахунку функції необхідно вміти швидко знаходити значення біноміальних коефіцієнтів C_n^k. Це можна зробити за допомогою попереднього підрахунку усіх значень факторіалів від до , та відповідних зворотніх факторіалів. Такий підрахунок може бути виконаний за час O(n + \log mod) або ж O(n \log mod), після чого значення C_n^k можна знаходити за .

Загальна складність — O(n + \log mod) чи O(n \log mod) в залежності від реалізації підрахунку зворотніх факторіалів.