Условия: http://contests.snarknews.info/files/snws11/probs/day5.pdf
Результаты: http://contests.snarknews.info/index.cgi?data=snws11/standing5&menu=index&head=index&mod=snws11&class=snws11
Задача А.
Сначала заменим все числа на A%mod, так как понятно нас интересует только остаток, затем добавляем сначала все числа с одним остатком, затем с другим итд. Допустим, что сейчас добавляются числа с отстатком m, а до этого уже были добавлены какие-то числа с другими остатками. Поддерживаем динамику d от двух параметров, где d[v][q] = количество последовательностей из уже добавленных чисел таких, что есть ровно v пар чисел с одинаковым остатком, НЕ равным m, стоящих рядом, и q пар чисел с остатком, равным m, стоящих рядом.
Кроме того, двигаясь вправо поддерживаем: n - сколько уже вообще добавлено чисел, и r - сколько уже вообще добавлено чисел с текущим остатком. Теперь, закрепим v и q. У нас есть три опции:
1. Поставить число между двумя одинаковыми числами, не имеющими остаток m. Таких вариантов, очевидно, v, и такое действие уменьшит v
nd[v-1][q] += d[v][q] * v
2. Поставить число между или рядом с числом с остатком m. Это увеличит q. Таких вариантов, если подумать, 2*r-q:
nd[v][q+1] += d[v][q] * (r*2-q)
Наконец, поставить число в любую другую позицию. Это не изменит ни q ни v. Это все оставшиеся варианты, то есть n+1 - v - (r*2-q)
nd[v][q] += d[v][q] * ( n + 1 - v - (r*2-q) ).
Потом, когда остаток от деления меняется, добавляем числа с предыдущим остатком к старым:
nd[v+q][0] += d[v][q];
В конце ответ будет в d[0][0] - потому что не должно быть никаких чисел с равным остатком рядом.
Задача B.
Я занумеровал вершины в порядке выхода из DFS, и вывел их по убыванию этой величины.
Задача C.
Единственное ограничение, данное нам -- это то, что кратность ребер не превышает четырех. В частном слуачае, когда вес всех ребер равен единице, это будет задача на матричную теорему Кирхгофа, которая решается за N^3.
Я упускаю что-то очень важное :о)
Задача F.
Очевидно, сами числа не важны, важна только их длина. Нам надо понять, сколько битов понадобится, чтобы представить число с записью 10^K в системе счисления B. Это, если я правильно помню, равно floor( K*log(B)/log(2)+1 ).
Comments (5)
0
