06/04/2025 13:04:06

Рабочее место участника

Задачи

836. Ломаные

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На окружности отметили

$N$ точек и пронумеровали их последовательно числами от 1 до

$N$ . Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами

$i$ и

$j$ .

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

Во входном файле записано три натуральных числа

$N$ ,

$i$ ,

$j$ (

$2\ ≤\ N\ ≤\ 2\ 000$ ,

$1\ ≤\ i\ <\ j\ ≤\ N$ ).

В выходной файл надо вывести остаток от деления количества ломаных на

$10^9$ .

Пример ввода 1

4 1 3

Пример вывода 1

Пример ввода 2

5 1 4

Пример вывода 2

В первом примере ломаные такие: (1 3), (1 2 3), (1 2 4 3), (1 4 2 3), (1 4 3)
Решения, верно работающие при

$N\ ≤\ 100$ , будут набирать не менее 70 баллов.
Решения, верно работающие при

$N\ ≤\ 10$ , будут набирать не менее 30 баллов.
Московская городская олимпиада школьников по информатике, 2008

17/03/2008	Школьные сборы, дорешивание (2D)
18/03/2008	Школьные сборы, день 2 (D)