Or 12 minutes after the contest, at 12:12 :)

Судя по закомментированному main`у в решении ir5, это просто баян с какого-то OJ.

Переберем, сколько до k-го шага было циклов "по 3", сколько "по 2", и остается сколько-то "по 1". Это медленное решение за n^2. Ну и теперь свернем часть сумм чтобы стало за n или за 1.

Перебираем количество красных шариков x, взятых до k-того взятого шарика, и смотрим на количества взятых зелёных и синих y и z до k-того взятого шарика. Ясно, что y + z = k - x - 1. Дальше разбираем 3 случая:

1. y, z < x;
2. y = x, z < x или y < x, z = x;
3. y = x, z = x.

В каждом случае нужно посчитать, сколькими способами можно построить y и z, а также дополнить каждый из трёх цветов с помощью разных формул, за константное время.

Я решал так: перебрал номер итерации алгоритма когда у нас убирается k-ая штука и при этом она красная. Тогда я знаю сколько было убрано других до. Ну и дальше разбор случаев в стиле: 1) оба цвета ещё остались после этой итерации 2) все шары других видов убраны до этой итерации 3) Один не красный исчезает второй остается. 4) когда может быть что не красные могут быть либо убраны до этой итерации, либо остается ещё 1 ровно 1 цвет.

И в каждом случае можно очень легко посчитать.

Можно динамикой [порядковый номер шара, который сейчас вылетит][маска цветов, которые ещё не вылетели][номер шага программы]

Я решал динамикой :)

dyn[i][0] означает число способов взрывать шарики так, что на i-м месте стоит красный и что у нас могли ещё остаться шарики трех цветов (т.е. прежняя последовательность выглядит как rgbrgb...rgbr)

dyn[i][1] означает число способов взрывать шарики так, что на i-м месте стоит красный и у нас могли остаться шарики только двух цветов.

dyn[i][2] — то же самое, но остались только красные шарики

dyn[i+3][0] = dyn[i][0];
dyn[i+2][1] = dyn[i][1] + dyn[i][0]*2;
dyn[i+1][2] = dyn[i][2] + dyn[i][1] + dyn[i][0];

Когда досчитали до k-го шарика, осталось выяснить сколькими способами можно заполнить остаток последовательности. Получаем:

ans = dyn[k][0]*(n-k+1)*(n-k+2)/2;
ans += dyn[k][1]*(n-k+1);
ans += dyn[k][2];

Кстати, я очень удивлен, что так мало фейлов по медиуму — почти все сворачивали суммы, в каждой из которых надо аккуратно разобраться с округлением, не верится что так мало людей не налажало в этом.

В начале поставим старший бит во всех числах, затем следующий за ним и т.д.. Итак, если на какой-то позиции префикс числа меньше, чем максимальный допустимый, то остаток (суффикс) этого числа может быть любым. А это значит, что для любой комбинации суффиксов всех остальных чисел будет ровно одно значение суффикса текущего числа, которое нам подходит.

Переберем номер бита, на котором впервые префикс какого-то числа стал меньшим, чем его максимальное допустимое значение. Для всех предыдущих битов должно выполняться условие, что их xor во всех числах из инпута совпадает с соответствующими битами числа n. Чтобы найти количество способов поставить текущий бит, можно воспользоваться следующей динамикой:

f(i, j, k) -- количество способов выбрать текущий бит и все следующие за ним в первых i числах, при условии что xor текущего бита в них равен j, а k говорит, встретилось ли нам уже число, для которого мы выбрали 0, хотя текущий бит в нем 1. Эта динамика считается за O(m), где m -- количество чисел.

Получаем решение за O(mk), где k -- битовая длина числа.

http://apps.topcoder.com/wiki/display/tc/SRM+564