Посчитать кол-во способов представить число в виде произведения чисел фибоначи

Сегодня был на олимпиаде по информатике, там была задача посчитать кол-во способов представить число в виде произведения чисел фибоначи.

Например: Число: 8, Ответ: 2, Тк 2*2*2=8 и 8=8

Числа фибоначи для удобства: 1 1 2 3 5 8 13 21 34 55

К сожалению, код не разрешили с собой забрать, а с телефона сейчас писать не хочу.

Итак, что я написал там:

Набрал 32 балла на пайтон, переписал на С++ - все равно 32 балла. Зря время потратил(

Я написал функцию, которая создает массив чисел Фибоначи до n

И функцию check(num, layer=0) В ней определил базовый случай - если число num есть в массиве фибоначи, то увеличиваю count на 1.

А иначе я вызывал рекурсивно check(num/fibNumber, layer+1)

Но тогда 40 = 5 на 8 и 8 на 5 - 2 варианта, а это 1 вариант.

Тогда я создал глобальный массив layers, в который добавлял из базового случая переменную layer, которая увеличивается для каждого деления на 1. И тогда просто не увеличивал счетчик, если такое кол-во множителей уже было.

Алгоритм работвет, но не вкладывается по времени в ограничение 1.2 секунды. Ни на пайтоне, ни на cpp.

Как можно решить такую задачу эффективнее?

Ограничения: 1.2 сек 512мб памяти

Python 3.1 (не pypy) Gnu c++ ... - точно не помню