Текущ брой на Списание ИнфоМан
 


Зимни Математически Състезания 2005, Задача A3. ПРЕГРАДА

Условието на задачата може да прочетете тук.

Решение

Решаваме задачата по метода на динамичното оптимиране. Нека е дефинирана функция T(P,Q), която връща колко са пермутациите на P елемента, в които има точно Q намаляващи подредици. Тогава T(N,K) е отговорът на задачата. Допускаме, че когато искаме да изчислим T(P,Q) сме изчислили всички стойности T(R,S), за R<P, S<=Q. Да разсъждаваме по следния начин. Нека имаме една пермутация на P-1 елемента и започнем да добавяме числото P на всички възможни места. Тогава ако го добавим някъде във вече обособена намаляваща подредица, тя ще се разцепи на две, а ако го добавим точно преди началото на намаляваща подредица, броят на намаляващите редици в пермутацията ще се запази. Освен това поради начина на добавяме няма да повторим пермутации на P елемента. Понеже имаме изискването редиците да бъдат точно Q на брой, а местата, на които няма промяна в броя редици, са точно Q, то за T(P,Q) получаваме следната рекурентна формула:

T(P,Q) = Q*T(P-1,Q) + (P+1-Q)*T(P-1,Q-1).

Освен това

Т(1,1) = 1,

понеже ако имаме един единствен елемент, броят начини да образуваме една редица е точно 1.

Сложността на описаното решение и от гледна точка на време, и от гледна точка на памет, е O(N2).

Примерна реализация:

#include <stdio.h>

#define MOD 1020847
#define MAXN 2048

int t[MAXN][MAXN];

int main () {

	int N,P,i,j;

	scanf("%d%d",&N,&P);

	t[1][1] = 1;

	for (i=2;i<=N;i++)
		for (j=1;j<=i;j++)
			t[i][j] = ((j * t[i-1][j])%MOD + 
				 ((i + 1 - j)*t[i-1][j-1])%MOD)%MOD;

	printf("%d\n",t[N][P]);

	return 0;
}

Автор: Слави Маринов


обратно към брой 27