Зимни Математически Състезания 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
|