Підрахунок ґратчастих чотирикутників#1710
У наведеній нижче сітці 10 \times 10 ви можете побачити п'ять різних ґратчастих чотирикутників. (Ґратчастий чотирикутник — це чотирикутник, вершини якого мають цілі координати, сторони перетинаються лише у вершинах, і жоден із внутрішніх кутів не дорівнює градусам.) Звісно, це лише декілька з мільйонів ґратчастих чотирикутників, які можна намалювати на сітці 10 \times 10. Дано сітку розміром N \times N, ваше завдання — визначити кількість різних ґратчастих чотирикутників, які можна побудувати на цій сітці.
Вхід містить не більше тестових випадків. Кожен рядок містить одне ціле число (0 < N < 121). Вхід завершують рядком, у якому дорівнює нулю.
Для кожного рядка вхідних даних виведіть відповідь у окремому рядку. Кожен рядок виводу повинен містити два цілих числа: значення з вхідного рядка та кількість ґратчастих чотирикутників для сітки N \times N. Гарантується, що відповідь вміститься у -бітне знакове ціле число.
Попередження: У цієї задачі немає альтернативного розв'язку, окрім авторського. Для перевірки тестових випадків можна написати брутфорс-розв'язок. Таким чином, ви можете знайти всі відповіді для малих сіток (до 22 \times 22), якщо запустите програму приблизно на годин.
Підказка: Обмеження часу для цієї задачі — секунди. Попередній розрахунок може бути кращим варіантом, якщо вам складно знайти ефективне рішення. У будь-якому разі, брутфорсний метод працюватиме приблизно років на комп'ютері Pentium IV з частотою ГГц.
Приклад 1