Комментарии 3
По 1-й задаче — N-ое число Фибоначчи (с условиями — например не само число, которое ни в какие ворота не влезет, а его остаток от деления на MOD=10^9+7) можно еще нескучно находить за O(log(N)) времени, то есть почти бесплатно, даже если N = 10^9 или 10^18 =)
Матрица преобразования размером 2x2 с одним нулем и тремя единицами меняет (a, b) на (b, a + b), то есть на следующую пару Фибоначчи.
Чтобы X раз применить эту матрицу к (a, b) = (0, 1), можно не перемножать по очереди, а сразу найти X^(N-2) бинарным возведением в степень, и применить! После каждого умножения надо только ко всем элементам применить %= MOD.
Если говорить о тех же соревнованиях, то там память изрядно ограничена, и зачастую используя динамическое программирование получить высший балл за задачу нельзя.
Но сама по себе техника интересная. Требует изрядно поломать мозг, чтобы к ней привыкнуть.
В таких задачах часто бывает так, что массив действительно не лезет в память, но есть лазейка — функция для вычисления ответа может выглядеть примерно так:
int arr[N][K];
/* ... */
arr[i][j] = arr[i + 1][j] * 3 + arr[i + 2][j - 1] * 5 + arr[i][j + 1];
/* ... */
cout << arr[i][j] << endl;То есть в этом примере не имеет смысла хранить массив именно [N][K] — подойдет [3][K] и считать надо "с конца", без рекурсии. Тогда вместо arr[x][y] надо писать arr[x % 3][y], и так далее.
Динамическое программирование в олимпиадных задачах