Какой-то идиот задачу составлял.
Во-первых, для N<60 ответ помещается в 64-битный целочисленный тип, который есть сейчас практически во всех языках программирования. Тут не надо ничего придумывать для избегания переполнения.
Во-вторых, чтобы избежать переполнения, в таких задачах обычно просят выдать ответ по какому-то большому модулю. И последнее, как ответ может получиться нецелым - это просто загадка. Пример решения явно неверен.
А так, динамическое программирование тут простое: Пусть F(N,K) - сколько существует
невзрывоопасных стопок длины N, таких что в конце есть ровно K опасных контейнеров (очевидно, 0 <= K < 4). Это не совсем прям то, что вам нужно в задаче, но количество опасных стопок - это количество всех стопок (2^N) минус количество невзрывоопасных, поэтому это ДП нам подходит.
Пересчет очень прост:
F(N,K>0) = F(N-K,0)
F(N,0) = F(N-1,0)+F(N-1,1)+F(N-1,2)+F(N-1,3)
Если на конце K плохих контейнеров, то до этого точно должен быть хороший контейнер. Если на конце стоит хороший контейнер - то до него может быть 0..3 плохих контейнера.
База:
F(0,0) = 1, F(0, K>0) = 0
Ответ:
2^N - F(N,0)-F(N,1)-F(N,2)-F(N,3) 
