Участник:Тихмонатор Тестбот/Полигон3

Предисловие. Пусть нам надо посчитать $\sum _{i=1}^{n}{i!}=1!+2!+3!+...+(n-1)!+n!$. Можно, кончено, считать в лоб, высчитывая по очереди все факториалы и складывая их. Однако зачем заставлять компьютер перемножать, допустим, первые 50 чисел (высчитывая $50!$), если до этого мы считали $49!$, и нам нужно всего лишь домножить это дело на 50? Поэтому логичнее куда-то запоминать значения посчитанного факториала $k!$, чтобы потом умножить его на $k+1$. В результате мы получим цикл вида for(int i=1; i<=n; i++){a=a*i; s=s+a;} Здесь $s$ — высчитываемая сумма, $a$ — «хранилище» наших факториалов.

Ту же идею попытаемся использовать, высчитывая выражение $\prod _{i=1}^{n}{(x^{i}\sum _{j=1}^{i}C_{n}^{j}{\frac {1}{j!}})}$. Только если в примере выше нам удалось обойтись одним «хранилищем» (там, где мы запоминали факториалы), то здесь их понадобится несколько.

Распишем произведение $p=\prod _{i=1}^{n}{(x^{i}\sum _{j=1}^{i}C_{n}^{j}{\frac {1}{j!}})}$: $p=(x^{1}\sum _{j=1}^{1}C_{n}^{j}{\frac {1}{j!}})\times (x^{2}\sum _{j=1}^{2}C_{n}^{j}{\frac {1}{j!}})\times (x^{3}\sum _{j=1}^{3}C_{n}^{j}{\frac {1}{j!}})\times ...\times (x^{n-1}\sum _{j=1}^{n-1}C_{n}^{j}{\frac {1}{j!}})\times (x^{n}\sum _{j=1}^{n}C_{n}^{j}{\frac {1}{j!}})$. В примере с факториалами нам надо было посчитать сумму штучек вида $k!$, а здесь — произведение штучек вида $x^{i}\sum _{j=1}^{i}C_{n}^{j}{\frac {1}{j!}}$. Идея та же, только сложнее. И, как в примере мы вычисляли факториал числа $(k+1)!$ через $k!$, так и здесь попробуем выразить $x^{k+1}\sum _{j=1}^{k+1}C_{n}^{j}{\frac {1}{j!}}$ через $x^{k}\sum _{j=1}^{k}C_{n}^{j}{\frac {1}{j!}}$.

Для этого распишем сумму: $x^{k}\sum _{j=1}^{k}C_{n}^{j}{\frac {1}{j!}}=(x^{k}C_{n}^{1}{\frac {1}{1!}})+(x^{k}C_{n}^{2}{\frac {1}{2!}})+(x^{k}C_{n}^{3}{\frac {1}{3!}})+...+(x^{k}C_{n}^{k}{\frac {1}{k!}})$. Обозначим это выражение за $R_{k}$.

Теперь распишем то, что мы хотим получить, то есть сумму $R_{k+1}=x^{k+1}\sum _{j=1}^{k+1}C_{n}^{j}{\frac {1}{j!}}=(x^{k+1}C_{n}^{1}{\frac {1}{1!}})+(x^{k+1}C_{n}^{2}{\frac {1}{2!}})+(x^{k+1}C_{n}^{3}{\frac {1}{3!}})+...+(x^{k+1}C_{n}^{k}{\frac {1}{k!}})+(x^{k+1}C_{n}^{k+1}{\frac {1}{(k+1)!}})$. Если внимательно посмотреть, то первые $k$ слагаемых у этих двух сумм практически одинаковы, отличается лишь степень при $x$: в $R_{k+1}$ она на единичку больше. Кроме того, в $R_{k+1}$ имеется лишнее слагаемое $(x^{k+1}C_{n}^{k+1}{\frac {1}{(k+1)!}})$. Получается, что $R_{k+1}=R_{k}x+x^{k+1}C_{n}^{k+1}{\frac {1}{(k+1)!}}$. Обозначим $x^{k+1}C_{n}^{k+1}{\frac {1}{(k+1)!}}$ за $S_{k+1}$.

Вот тут появляется отличие от примера с факториалами. Там мы обходились одним «хранилищем» посчитанных ранее значений, с помощью содержимого которого получали новое слагаемое. Алгоритм был таков: взять число из «хранилища», слегка его изменить (домножить на $i$ — получить актуальный факториал), прибавить результат к сумме. В этом же примере таких хранилищ необходимо два — в одном будет храниться число $R_{i}$, в другом — $S_{i}$. Удлиняется и алгоритм: мы возьмём число $S_{i}$, изменим его, чтобы получить $S_{i+1}$, затем возьмём $R_{i}$, с помощью посчитанного уже $S_{i+1}$ превратим $R_{i}$ в $R_{i+1}$, и затем умножим произведение, которое мы высчитываем, на $R_{i+1}$. Каким образом превращать $R_{i}$ в $R_{i+1}$, мы уже знаем: $R_{i+1}=R_{i}x+S_{i+1}$. Осталось выяснить, как превращать $S_{i}$ в $S_{i+1}$.

Имеем: $S_{i+1}=x^{i+1}C_{n}^{i+1}{\frac {1}{(i+1)!}}=x^{i+1}{\frac {n!}{(i+1)!(n-i-1)!}}{\frac {1}{(i+1)!}}=$
$=x^{i+1}({\frac {n!}{i!(i+1){\frac {(n-i)!}{n-i}}}}{\frac {n-i}{i+1}}){\frac {1}{(i+1)!}}=x^{i}x({\frac {n!}{i!(n-i-1)!}}{\frac {n-i}{i+1}}){\frac {1}{i!}}{\frac {1}{i+1}}=$
$=(x^{i}{\frac {n!}{i!(n-i)!}}{\frac {1}{i!}})(x{\frac {n-i}{i+1}}{\frac {1}{i+1}})$. Но можно заметить, что первый множитель является $S_{i}$, поэтому $S_{i+1}=S_{i}(x{\frac {n-i}{(i+1)^{2}}})$.

Вот мы и установили, как выражается $S_{i+1}$ через $S_{i}$. Теперь мы можем задать значения $S_{0}=1$ и $R_{0}=0$, после чего по имеющимся формулам $S_{i+1}=S_{i}(x{\frac {n-i}{(i+1)^{2}}})$ и $R_{i+1}=R_{i}x+S_{i+1}$ найти $S_{1}$ и $R_{1}$ — так мы найдём первый множитель. По тем же самым формулам, но уже используя $S_{1}$ и $R_{1}$, мы находим $S_{2}$ и $R_{2}$ — второй множитель. Действуя так далее до $n$, мы находим все множители, входящие в состав произведения, которое нам необходимо посчитать.

Ну а цикл вообще должен иметь следующий вид:

for (int i=1;i<=n;i++)
{
s=s*x*(n-i+1)/(i*i);
r=r*x+s;
p=p*r;
}