Условие: Необходимо посчитать количество "счастливых" билетов с заданной суммой цифр, среди тех, номер которых состоит из 2*N разрядов. "Счастливым" является билет, у которого сумма первых N цифр равна сумме N последних цифр.
Технические условия: Во входном файле находятся два числа разделенных пробелом: первое - N (1<=N<=50); второе - сумма цифр интересующих нас билетов (неотрицательное число не превосходящее 1000). В качестве ответа необходимо вывести найденное число "счастливых" билетов.
Примеры входных и выходных файлов: Input.txt 2 2 Output.txt 4
--------------- 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 ----------------
{$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.
