Олимпиадная информатика-2013

Задача « Беспорядки »

На книжной полке известного ученого Василия Шекспирова беспорядочно стоят N книг из его полного собрания сочинений. Каждый том имеет свой номер - число от 1 до N. В целях научности и систематичности Вася решил оценить степень беспорядка расставленных книг. С его точки зрения два тома образуют беспорядок, если том с меньшим номером стоит правее тома с большим номером. Степенью беспорядка Вася назвал общее число К всех беспорядков в расстановке. Например, в расстановке (2,1,5,3,4) беспорядки образуют пары томов (2,1), (5,3) и (5,4), поэтому степень беспорядка такой расстановки равна 3. Василий заметил, что есть и другие расстановки из 5 книг с той же степенью беспорядка 3, - например, (2,1,4,5,3) и (1,3,4,5,2) и другие. Помогите Василию подсчитать общее число расстановок из N книг с заданной степенью беспорядка К.?

Формат входного файла input.txt Первая строка содержит два разделенных пробелом числа N и К - общее число книг на полке и степень беспорядка (2 < N< 10000, 0 < К< 30).

Формат выходного файла output.txt В единственной строке запишите требуемое количество расстановок из N книг по модулю (109 + 9). Если нет ни одной расстановки с заданной степенью беспорядка, - выведите 0.

function T(N: longint; К: longint): int64;
begin
if К < 0 then begin T := 0; exit; end;
if К = 0 then begin T := 1; exit; end;
if К = 1 then begin T := N - 1; exit; end;
if (K > N*(N - 1) cliv 2) then begin T := 0; exit; end;
if table[N,K] > -1 then begin T := table[N,K]; exit; end;
Result ;= (T(N - 1,K) + T(N,K - 1) - T(N - 1,K - N)) mod 1000000009;
table[N, K] := Result;
end;
Вызов этой функции из основной программы:
begin fillchar(table, sizeof(table), -1);
write(output, T(N,K));
end.


close
 

Разбор задачи №1 "Беспорядки"

Пусть T(N, К) - количество расстановок из N книг с заданной степенью беспорядка К. Для функции T(N,K) справедливы рекуррентные соотношения: UN, К) = T(N, K-1) + T(N- 1 ,К) - UN - 1 ,К- N). с начальными условиями T(N, 0) = 1, T(N, 1) = N- 1 и T(N, К) = 0 при К< 0.

Действительно, пусть перестановка (аь аъ ..., aN) содержит К инверсий и N > К. Множество всех перестановок порядка N разобьем на два класса - те, у которых aN = N, и те, у которых о, = N, где / < N. Элементы первого класса являются, по сути, перестановками порядка N - 1, поэтому количество таких перестановок равно T(N - 1, К).

Для перестановок второго класса мы можем поменять местами о, и а1+1, получив перестановку порядка N с К- 1 инверсиями.

Обратно, в любой перестановке порядка N с К- 1 инверсиями первый элемент отличен N, так как иначе количество инверсий будет не менее N - 1 > К. Значит, поменяв местами элемент N с предыдущим, мы получим перестановку с К инверсиями. Следовательно, количество перестановок во втором классе равно T(N, К - 1).

Отсюда при N> К получаем T(N, К) = T(N, К - 1) + T(N - 1, К). Доказательство рекуррентного соотношения при N < К можно провести аналогично (разбивая множество всех перестановок на N классов в зависимости от положения элемента N).

Теперь осталось организовать рекурсивную функцию T(N, К), сохраняя все ранее подсчитанные значения функции в табличном массиве table[1.. 10000, 0..30]: