Надо найти количество построений дорог между $N$ центрами, где $N \le 100$.

Можно представить сеть центров, как ориентированный граф с $N$ вершинами.

Максимум дорог(неориентированных) между вершинами такого графа может быть $C_N^2 = \frac{N(N-1)}{2}$.

И у каждой дороги($u - v$) будет три состояния:

$u \to v$.

$v \to u$.

дорог между $u$ и $v$ вообще нет.

То есть ответ: $3^{\frac{N(N-1)}{2}}$. Так как ответ может быть большим, надо использовать

длинную арифметику.

Надо найти количество таких заполнений бланков ответа из $N$ вопросов по $K$ ответов, чтобы ни в

одном варианте заполнения не было ни одного правильного ответа.

Нам дано какое-то множество правильных ответов к каждому вопросу, и мы можем выбрать любой

вариант ответа, кроме правильного. Т.е., если есть $K$ ответов, то один из них правильный, а

остальные $K-1$ неправильные. Всего вопросов $N$ и мы можем выбрать любые $K-1$ неправильных

ответов. Значит ответ: $(K-1)^{N}$. Здесь также нужно воспользоваться длинной арифметикой.

По этой картинке можно понять, что эта задача решается арифметической прогрессией. Просто посчитайте желтые линии!!!

И у вас получится 1,2,3,4

Это и есть арифметическая прогрессия

Формула $\frac{(a_1+a_N)*N}{2}=$sum of $a_1...a_N$

в нашем случае получается $N=n-1$, и мы знаем, что $a_1$ всегда равняется 1, и $a_N=n-1$

$\frac{(1+n-1)*(n-1)}{2}=$sum of $a_1...a_N$

Формула получается $\frac{n*(n-1)}{2}=$sum of $a_1...a_N$

Обозначим sol(k,m) сколько дней проживет Вася у Деда если рассказывать по М сказок в день, а всего К сказок; если К<М то sol(K,M)=0; если М=1 то sol(K,M)=K; иначе sol(k,m)=sol(k-1,m-1)+sol(k-2,m-1)+sol(k-3,m-1)...+sol(2,m-1)+sol(1,m-1);

Задача в том чтобы выбрать м сказок из к. С(а, б) = б! / ((б-а)!а!) = количество способов выбрать а чисел из б. С(м, к) = ответ = к!/((к-м)!м!)

Решим арифметикой! кол рукопожатий : 1-ученик вначале некому не пожимает руку а1=0 N-ученик пожимает руку n-1 мальчикам an=n-1 оттуда сумма рукопожатий S=(a1+an)*n / 2

кол приветов: каждая девочка говорит Привет другой девочке используем формулу выше но уберем /2 поскольку рукопожатие одно а приветов два a1=0;am=m-1 s1=(a1+am)m Также каждая девочка говорит Привет каждому мальчику, а мальчик отвечает также поэтому s2=mn*2;

И того кол приветов = s1+s2;

Можно эту задачу еще решить комбинаторикой. Сначала считаем сколько 3 можно поставить a=Math.floor(n/3), после считаем сколько 1 осталось b=n%3, а в конце смотрим сколько может быть 0 с=k-(a+b) потом запускаем функцию которая находит все перестановки n!/(a!b!c!);

Заводим цикл и бьем 3 на 1 если это возможно, то есть a--; b+=3; c-=2;

Опять запускаем функцию и каждый раз прибавляем к результату.

Разбор

Здесь можно применить динамическое программирование. Нам потребуется двумерный массив A(i,j), где будем хранить ответы.
Вы можете идти вниз или вправо. Значит A(i,1)=1, при i=1..n и A(1,j)=1, при j=1..m. Дальше, на A(i,j), при 1<=n, можно идти способами A(i-1,j) и A(i,j-1). Ответом будет a[n,m]

Но есть другой способ решения задачи, комбинаторикой. Формула такая:
C((n-1)+(m-1),(n-1))=количество путей

C(i,j)=i!/((i-j)!j!)
n!=12...n