Разбор

Перепишем заданную сумму в виде:

1 \cdot C_{n}^{0} + 2 \cdot C_{n}^{1} + 3 \cdot C_{n}^{2} + ... + (n + 1) \cdot C_{n}^{n} =

(C_{n}^{0} + C_{n}^{1} + C_{n}^{2} + ... + C_{n}^{n}) + 1 \cdot C_{n}^{1} + 2 \cdot C_{n}^{2} + ... + n \cdot C_{n}^{n}

Сумма в скобках равна $2^{n}$ . Если в формуле бинома Ньютона

(a + b)^{n} = i = 0 \sum n C_{n}^{i} a^{i} b^{n - i}

положить $a = b = 1$ , то получим соотношение: $(1 + 1)^{n} = \sum_{i = 0}^{n} C_{n}^{i} 1^{i} 1^{n - i}$ , или

2^{n} = i = 0 \sum n C_{n}^{i} = C_{n}^{0} + C_{n}^{1} + ... + C_{n}^{n}

Вычислим оставшуюся сумму:

1 \cdot C_{n}^{1} + 2 \cdot C_{n}^{2} + ... + n \cdot C_{n}^{n} =

1 \cdot \frac{n !}{1 ! \cdot ( n - 1 )!} + 2 \cdot \frac{n !}{2 ! \cdot ( n - 2 )!} + ... + n \cdot \frac{n !}{n ! \cdot ( n - n )!} =

n \cdot (\frac{( n - 1 )!}{0 ! \cdot ( n - 1 )!} + \frac{( n - 1 )!}{1 ! \cdot ( n - 2 )!} + ... + \frac{( n - 1 )!}{( n - 1 )! \cdot ( n - n )!}) =

n \cdot (C_{n - 1}^{0} + C_{n - 1}^{1} + ... + C_{n - 1}^{n - 1}) = n \cdot 2^{n - 1}

Таким образом, ответ равен $2^{n} + n \cdot 2^{n - 1} = (n + 2) \cdot 2^{n - 1}$ .

Пример

Вычислим ответ для $n = 3$ . При непосредственном вычислении:

1 \cdot C_{3}^{0} + 2 \cdot C_{3}^{1} + 3 \cdot C_{3}^{2} + 4 \cdot C_{3}^{3} = 1 \cdot 1 + 2 \cdot 3 + 3 \cdot 3 + 4 \cdot 1 = 1 + 6 + 9 + 4 = 20

При вычислении по формуле: $5 \cdot 2^{2} = 20$ .

Реализация алгоритма

Читаем входное значение $n$ .

scanf("%lld", &n);

Вычисляем и выводим ответ.

res = (1LL << (n - 1)) * (n + 2);
printf("%lld\n", res);

Реализация алгоритма – функция

Объявим массив для запоминания результатов: $d p [n] [k] = C_{n}^{k}$ .

int dp[31][31];

Функия Cnk вычисляет значение биномиального коэффициента $C_{n}^{k}$ .

int Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % 9929;
}

Основная часть программы. Читаем входное значение $n$ .

scanf("%d", &n);
memset(dp, -1, sizeof(dp));

Вычисляем указанную сумму.

res = 0;
for (i = 0; i <= n; i++)
  res += (i + 1) * Cnk(n, i);

Выводим ответ.

printf("%d\n", res);

Python реализация – функция comb

import math

Читаем входное значение $n$ .

n = int(input())

Вычисляем указанную сумму. Для вычисления биномиального коэффициента используем встроенную функцию comb.

res = 0
for i in range(n + 1):
  res += (i + 1) * math.comb(n, i)

Выводим ответ.

print(res)

Python реализация – функция

Функия Cnk вычисляет значение биномиального коэффициента $C_{n}^{k}$ .

def Cnk(n, k, dp):
  if n == k: return 1
  if k == 0: return 1
  if dp[n][k] != -1: return dp[n][k]
  dp[n][k] = Cnk(n - 1, k - 1, dp) + Cnk(n - 1, k, dp)
  return dp[n][k]

Основная часть программы. Читаем входное значение $n$ .

n = int(input())

Инициализируем все элементы двумерного списка dp значением $- 1$ . Список используем для запоминания результатов: $d p [n] [k] = C_{n}^{k}$ .

dp = [[-1 for _ in range(31)] for _ in range(31)]

Вычисляем указанную сумму.

res = 0
for i in range(n + 1):
   res += (i + 1) * Cnk(n, i, dp)

Выводим ответ.

print(res)

Python реализация – формула

Читаем входное значение $n$ .

n = int(input())

Вычисляем ответ $res$ по формуле.

res = (1 << (n - 1)) * (n + 2)

Выводим ответ.

print(res)