(-) mean, that all that I wanted to say is situated in theme
(+) mean, that "will be continue..."  :)

Yes formula interesting. My friend "create" it, and we get AC on contest, but we can't to prove it "strongly".

------
Sorry for bad English :)

>>The formula is very interesting.
 formula from Victor Barinov (TNU)
 f(1) = 0;                     (V1)
 f(n) = n*f(n-1) + (-1)^n;     (V2)
same as formula from Kit
 f(0) = 1;                     (K0)
 f(1) = 0;                     (K1)
 f(n) = (n - 1)*(f(n - 1) + f(n - 2)) (K2)
cose:
   from v2:
     (-1)^n    =  f( n )-  n  *f(n-1)
     (-1)^(n+1)=  f(n+1)-(n+1)*f( n )
  sum they:
      0 = f(n+1) +f(n)-(n+1)*f(n)-n*f(n-1)
   or 0 = f(n+1)- n*f(n)-n*f(n-1)
   or f(n+1)=n*(f(n)+f(n-1))
   or f(n)=(n-1)*(f(n-1)+f(n-2))  That is   (K2)

???Victor Barinov (TNU) can you explain how you thot for find V2???

В варианте :
h(n)=f(n,0);    (Tx)
f(0,b)=b!;      (T0)
f(1,b)=b*b!;    (T1)
f(a,b)=(a-1)*f(a-2,b+1)+b*f(a-1,b);T(2)

Можно расуждать так
пуст (a) детей ещё могут нарватся(вытащить из оставшихся кучи свой хлам) и (b) детей не нарвутся уже точно (их презент уже нашёл нового хозяина).
Расмотрим все возможные варианты ребёнка из группы а:
0) выташил свой, 1 случай -> Дальше лудше и не представлять:)
1) выташил презент  кого то другого из a, (a-1 случай )-> тем самым сделав того б :) то есть (a-1)*f(a-2,b+1),
2) вытащил презент кого то из b (b случаев) ->
a уменшилось на 1,число b осталось преждним: b*f(a-1,b)

и граничные случаи:
0)когда все подарки чужие (то есть их бывшие владельцы уже взяли чьёто добро и ушли с воспитателем на прогулку):
 f(0,b)=b!
1) когда остался 1 хозяин , остальное чужое (хозяин может выбрать один из чужих(b вариантов), и случай сведется к предыдущему
  f(1,b)=b*b!

>>if use this formula and BIG NUMBERS we have TLE. Послано >>Lifanov 24 апреля 2005 18:19
>>for n>100 it will be work very slow :(
 при использовании таблицы предвычислений!!!(то есть  считать одно и тоже конкретное f(a,b) только раз )и арифметики BIGNUM tle не будет, не должно быть, э ну ...
А вы Lifanov использовали таблицу или всё в рекурсии?




>>>F(n)=(n-1)! +C(n,2)*F(2)*F(n-2)+C(n,3)*F(3)*F(n-3)
 ...C(n,n/2)*F(n/2)*F(n-n/2)                         (L1)
it is solution , but how i solve this for n=1000 ??
???Lifanov can you explain how you thot for find L1???

Кто силён в рекурентностях, как свести Tx-T2 к K0-K2?

PS. Sorry, My Eng bad , so some Thot i write in rus, I understend that this site is for all piple , so if someWhy
translate(If need) , that shud be great