e-olymp 8651. Браслети (Bangles)

Задача взята з сайту e-olymp

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). ($4 \leqslant N \leqslant 300$). У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Тести

Inputs Outputs
1
5 7
1 3
1 4
2 4
2 5
3 4
3 5
4 5
2
2
4 4
1 2
2 3
3 4
1 4
1
3
5 5
1 2
2 3
3 5
1 4
1 5
1

Код

 

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

Посилання

ideone
e-olymp

4 thoughts on “e-olymp 8651. Браслети (Bangles)

Добавить комментарий