У меня только что зашло.

Заметим, что пары строк, которые нас интересуют — это такие строки, что одна из них получается циклическим сдвигом из второй. Давайте считать, сколько в алфавите из k букв есть строк длины N с количеством различных циклических сдвигов равных L. Это равносильно тому, что нам нужно посчитать, у скольки строк период равен L. Значит, L — делитель N. Для того, чтобы посчитать количество строк с периодом L, используем что-то вроде принципа включений-исключений:

f(L) = k^L-(сумма f(c) таких, что с — делитель L и с меньше L)

Чтобы узнать ответ, суммируем для каждого делителя N значение f(L) * L (для каждой строки ставим в пару ее циклический сдвиг)

Нет конечно. Верно то же удтверждение, если бы произведение 2х чисел было операцией минимума

Понятно, что одним ходом можно закончить игру, оставив какой-нибудь лист. Тогда рассмотрим логику первого игрока. Он может всегда взять какой-нибудь лист. Ответ — это вес самого тяжелого листа. Предположим, что первый игрок может взять больше, чем самый тяжелый лист. Тогда он первых ходом не закончить игру, а отрежет кусок дерева. Понятно, что одним разрезом удалить все начальные листья нельзя. Тогда второй игрок своим ходом закончит игру, так как тогда результат будет не больше, чем наибольший лист, а первый игрок хочет больше. Таким образом лучшая стратегия — это первым же ходом отрезать наибольший лист.