Задача взята з сайту 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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> using namespace std; typedef long long ll; const ll INF = 3e2+5; ll arr[INF][INF]; void power(ll n){ ll arr1[n][n]; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n; j++){ arr1[i][j]=0; for(int k = 0 ; k < n ; k ++){ arr1[i][j]+=arr[i][k]* arr[k][j]; } } } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n; j++){ arr[i][j]=arr1[i][j]; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,m ; cin>>n>>m; ll a,b; for(int i = 0 ; i < m ; i++){ cin>>a>>b; a--; b--; if(a!=b){ arr[a][b]++; arr[b][a]++; } } power(n); ll to_del[n]; for(int i = 0 ; i < n; i++){ to_del[i]=0; for(int j = 0 ; j < n; j++){ if(i==j){ arr[i][i] = 0; }else{ to_del[i]+=arr[i][j]; } } } power(n); ll answer =0; for(int i = 0 ; i < n ; i++){ answer +=arr[i][i]-to_del[i]; } cout<<answer/8; return 0; } |
Рішення
Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(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.