Отборочный раунд Russian Code Cup 2014: итоги и разбор задач

[Stmf]

Где достать такого робота, как на картинке?

[Mrrl]

Может ли кто-нибудь подсказать, как искать 1/(1+f) mod x^t с помощью БПФ? В голову приходит только вариант разложить его как (1-f)*(1+f^2)*(1+f^4)*..., и после каждого умножения обнулять старшие коэффициенты (как у произведения, так и у f^(2^m)). Но это будет O(t*log(t)^2).
Кстати, для первой части этой задачи (где считаются пути с возвращением) преобразование Фурье не нужно — там есть общая формула через биномиальные коэффициенты.