Сколькими способами можно разбить все натуральные числа от 1 до 10 так, чтобы в каждой паре сумма чисел не делилась ни на 2, ни на 3, ни на 5?

Предыдущий
вопрос Следующий
вопрос

Воспользуемся методом динамического программирования.

Пусть dp[i][mask] - это количество способов разбить числа от 1 до i (включительно), так чтобы множество чисел, на которое поделили все числа не равное mask, иначе -1.

dp[i][mask] = sum(dp[i - 1][new_mask]), где new_mask - числа-соосветствия, где mask & new_mask == 0.

Итоговый ответ - dp[10][(1 << 5) - 1].