Рекуррентные последовательности


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38131. Перестановка
Темы: Рекуррентные последовательности   

У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 1≤i≤N, i-ая точка задаётся двумя целочисленными координатами xi и yi (0≤xi,yi≤104).
Беси рисует некоторые отрезки между точками следующим образом:

Она выбирает некоторую перестановку p1,p2,…,pN из N точек
Она рисует отрезки между p1 и p2, p2 и p3, p3 и p1.
Затем для каждого целого i от 4 до N по порядку, она рисует отрезки прямых от pi до pj для всех j<i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 109+7.

Входные данные: 
Первая строка содержит N.
Каждая из последующих N строк содержит два разделённых пробелом целых числа xi и yi.

Выходные данные: 
Количество перестановок по модулю 109+7.
 

Примеры
Входные данные Выходные данные Пояснение
1 4
0 0
0 4
1 1
1 2
0 Никакая перестановка не сработает.
2 4
0 0
0 4
4 0
1 1
24 Все перестановки работают.
3 5
0 0
0 4
4 0
1 1
1 2
96 Одна из перестановок, удовлетворяющих свойству - (0,0),(0,4),(4,0),(1,2),(1,1).
Для этой перстановки
  • Сначала она рисует отрезки между каждой парой (0,0),(0,4), и (4,0).
  • Затем она рисует отрезки от (0,0), (0,4), и (4,0) до (1,2).
  • Наконец, она рисует отрезки от (1,2), (4,0), и (0,0) до (1,1).
Рисунок:

Перестановка не удовлетворяет свойству, если её первые четыре точки (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке.

ID 38639. Мячик на лесенке
Темы: Динамическое программирование: один параметр    Рекуррентные последовательности   

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.


Входные данные

Вводится одно число 0 < N < 31.


Выходные данные

Выведите одно число — количество маршрутов.
 

Примеры
Входные данные Выходные данные
1 4 7