Счастливые билеты 2 (3 уровень)

Условие:
Необходимо посчитать количество "счастливых" билетов с заданной суммой цифр, среди тех, номер которых состоит из 2*N разрядов. "Счастливым" является билет, у которого сумма первых N цифр равна сумме N последних цифр.

Технические требования:
Во входном файле находятся два числа разделенных пробелом: первое - N (1<=N<=50); второе - сумма цифр интересующих нас билетов (неотрицательное число не превосходящее 1000).
В качестве ответа необходимо вывести найденное число "счастливых" билетов.

Пример файлов входных и выходных данных:

Условию удовлетворяют билеты: 0101, 0110, 1001, 1010.

Решение: (by Boris Bukh <brbukh@yahoo.com>)
{$N+}
var N,S:LongInt;
    { V[i,j] - number of i-digit numbers having sum of digits=j
      Recurrence: V[0,j]=delta_0j
                  V[i,j]=sum(k=0..9,V[i-1,j-k])
                  implies
                  V[i,j]-V[i,j-1]=V[i-1,j]-V[i-1,j-10]
      Observation: V[i] is a function of V[i-1] only.
      We don't need to store V[i-1].
    }
    V:array[0..1,-10..1000]of Comp; { we store only two consecutive rows }
    i,j,k:Integer;
    sel:Integer;
begin
    Assign(Input,'input.txt');Reset(Input);
    Assign(Output,'output.txt');Rewrite(Output);
    Read(N,S);
    if (S and 1)<>0 then { S has to be even }
    begin
      WriteLn(0);Exit;
    end;
    S:=S div 2;
    FillChar(V,SizeOf(V),0);
    sel:=0;
    V[sel,0]:=1;
    for i:=1 to N do
    begin
      FillChar(V[sel xor 1],SizeOf(V) div 2,0);
      for j:=0 to S do { We have to do calculations up to S only }
      V[sel xor 1,j]:=V[sel xor 1,j-1]+V[sel,j]-V[sel,j-10];
      sel:=sel xor 1;
    end;
    WriteLn(V[sel,S]*V[sel,S]:0:0);
end.

--------------- cut ----------------
Можно вывести формулу для V[i,j] из рекуррентности. Обозначим через
F[i] обыкновенную производящую функцию для V[i,j] при фиксированном i.
Тогда F[0]=1, F[i]=F[i-1]*(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9) =>
=>F[i]=((1-x^10)/(1-x))^i=sum(x^10k*C_ik*(-1)^(i-k))*(-1)^i/(1-x)^i,
где C_ik - это биномиальный коэффициент.
Это дает нам еще один алгоритм. Мы можем вычислить левый множитель с
помощью хорошо известного алгоритма вычисления биномиальных
коэффициентов, а потом мы можем вычислить частичные суммы i раз. Этот
алгоритм чуть быстрее, но не намного. Он работает за время
(N^2/2+N*S)*(арифметика).
--------------- cut ----------------

--------------- cut ----------------
Ещё один алгоритм от Hellman'a (alexec@newmail.ru):

Нужно научиться раскладывать данное число (половину требуемой суммы) на N слагаемых, каждое из которых находится в интервале от 0 до 9. Дальше есть два пути:
1. Алгоритм может сгенерировать абсолютно все разложения (порядок слагаемых имеет значение). Тогда мы просто считаем их количество.
2. Алгоритм генерирует все разложения, которые нельзя получить друг из друга путем перестановок слагаемых. Тогда при нахождении очередного разложения надо увеличивать счетчик не на единицу, а на
N!
---------------
k0!*k1!*...*k9!
где k0, k1, ..., k9 - количество повторяющихся чисел в разложении.
Например, для такого разложения
1+2+2+3+3+3+3+8
получим
8!
----- = 840
2!*4!
Независимо от выбранного алгоритма в конце число надо возвести в квадрат, т.к. мы посчитали только количество возможных вариантов половинки билета. Билет же целиком может состоять из любой комбинации двух таких половинок.
--------------- cut ----------------