Выпишем числа Фибоначчи $F_0,F_1,\ldots,F_n$ и поставим между соседними числами знаки минус. Затем добавим $n$ пар скобок так, чтобы каждая пара соответствовала ровно одной операции вычитания. Иначе говоря, нужно перебрать все полные расстановки скобок в выражении
$$F_0-F_1-\cdots-F_n.$$
Для $n=3$ получается пять выражений. Их значения равны $-4,-2,0,2,-2$, поэтому их сумма равна $-6$. Обозначим через $A(n)$ сумму значений всех разных выражений. Из условия также известны
| Расстановка скобок | Значение |
|---|---|
| $(((F_0-F_1)-F_2)-F_3)$ | $-4$ |
| $((F_0-(F_1-F_2))-F_3)$ | $-2$ |
| $((F_0-F_1)-(F_2-F_3))$ | $0$ |
| $(F_0-((F_1-F_2)-F_3))$ | $2$ |
| $(F_0-(F_1-(F_2-F_3)))$ | $-2$ |
$$ A(3)=-6,\qquad A(10)=-177666, $$
$$ A(100)\equiv71792794\pmod{10^9+9}. $$
Требуется найти $A(10^7)$ по тому же модулю. Полное условие находится на странице Project Euler 1007.
Для малого $n$ хочется просто сгенерировать все варианты скобок, вычислить каждый и сложить результаты. Проблема обнаруживается сразу после подсчёта вариантов. Полная расстановка скобок — это полное упорядоченное бинарное дерево: листья идут слева направо в порядке $F_0,\ldots,F_n$, а каждая внутренняя вершина означает вычитание левого подвыражения и правого.
Таких деревьев ровно
$$ C_n=\frac{1}{n+1}\binom{2n}{n}, $$
где $C_n$ — $n$-е число Каталана. Последовательность начинается как $1,1,2,5,14,42,\ldots$, а асимптотически
$$ C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}}. $$
При $n=10^7$ речь уже не идёт ни о каком переборе. Но сами значения Фибоначчи пока тоже не помогают. Сначала нужно понять, что именно скобки делают со знаками.
В любом конкретном дереве результат остаётся линейной комбинацией исходных чисел:
$$ \varepsilon_0F_0+\varepsilon_1F_1+\cdots+\varepsilon_nF_n, \qquad \varepsilon_k\in\{-1,1\}. $$
Пусть $r_T(k)$ — число правых рёбер на пути от корня дерева $T$ к листу $F_k$. Каждый переход в правое поддерево добавляет внешний минус и переворачивает знаки всех листьев внутри. Поэтому
$$ \boxed{\varepsilon_T(k)=(-1)^{r_T(k)}}. $$
Это и есть первый настоящий поворот решения: вместо огромных числовых выражений можно считать только знаки листьев. На схеме ниже сплошное ребро ведёт влево, а штриховое — вправо и меняет знак. Ползунок меняет $n$, стрелки перебирают расстановки скобок. Нижняя строка показывает уже не одно дерево, а сумму знаков по всем деревьям выбранного размера.
Формулу для знака можно строго доказать индукцией по дереву. У одиночного листа знак равен $+1$. Если корень имеет вид $T=L-R$, то листья $L$ сохраняют локальные знаки, а каждый лист $R$ получает ещё один внешний множитель $-1$. Это ровно соответствует добавлению одного правого ребра на пути от корня. Никаких других способов изменить знак в дереве нет.
Обозначим через $\mathcal T_n$ множество всех полных упорядоченных бинарных деревьев с $n+1$ листьями и определим суммарный коэффициент листа
$$ s_{n,k}=\sum_{T\in\mathcal T_n}\varepsilon_T(k). $$
Тогда искомая сумма выражений равна
$$ A(n)=\sum_{k=0}^{n}s_{n,k}F_k. $$
Хранить всю таблицу $s_{n,k}$ до $n=10^7$ нельзя: она имеет квадратичный размер. Поэтому упакуем одну строку в полином
$$ P_n(y)=\sum_{k=0}^{n}s_{n,k}y^k. $$
Первые случаи легко проверить вручную:
$$ P_0(y)=1,\qquad P_1(y)=1-y,\qquad P_2(y)=2-2y, $$
$$ P_3(y)=5-5y+y^2-y^3. $$
Есть ещё один полезный смысл той же конструкции. Если вместо $F_0,F_1,\ldots$ поставить в листья $1,y,y^2,\ldots$, то значение каждого дерева станет полиномом от $y$, а сумма значений всех деревьев будет ровно $P_n(y)$. Поэтому полином одновременно хранит коэффициенты листьев и решает задачу для любой геометрической последовательности.
Подстановка чисел Фибоначчи в коэффициенты последнего полинома даёт
$$ A(3)=5F_0-5F_1+F_2-F_3=-6. $$
Пусть внешняя операция отделяет листья $0,\ldots,k$ от листьев $k+1,\ldots,n$. Слева находится дерево с $k$ операциями, справа — дерево с $n-1-k$ операциями.
Левый полином $P_k(y)$ повторяется для каждого из $C_{n-1-k}$ правых деревьев. В правой части локальные индексы нужно сдвинуть на $k+1$, то есть умножить на $y^{k+1}$, а внешний минус меняет все её знаки. Получается
$$ \boxed{ P_n(y)= \sum_{k=0}^{n-1} \left( C_{n-1-k}P_k(y) - C_ky^{k+1}P_{n-1-k}(y) \right) }. $$
Рекуррентность правильная, но пока бесполезная для большого индекса: внутри каждого шага остаётся свёртка по всем $k$. Прямой расчёт снова требует порядка $n^2$ операций.
Производящая функция чисел Каталана
$$ C(x)=\sum_{n\ge0}C_nx^n $$
удовлетворяет уравнению $C(x)=1+xC(x)^2$. Нужная ветвь с постоянным членом $1$ равна
$$ C(x)=\frac{1-\sqrt{1-4x}}{2x}. $$
Теперь введём двумерную производящую функцию
$$ P(x,y)=\sum_{n\ge0}P_n(y)x^n. $$
После умножения корневой рекуррентности на $x^n$ и суммирования две свёртки превращаются в обычные произведения:
Для первой части достаточно положить $m=n-1-k$:
$$ \sum_{n\ge1}\sum_{k=0}^{n-1} C_{n-1-k}P_k(y)x^n = xP(x,y)C(x). $$
Во второй части степень $y^{k+1}$ объединяется с $x^{k+1}$, поэтому каталановский ряд получает аргумент $xy$:
$$ \sum_{n\ge1}\sum_{k=0}^{n-1} C_ky^{k+1}P_{n-1-k}(y)x^n = xyC(xy)P(x,y). $$
$$ P(x,y)-1=xC(x)P(x,y)-xyC(xy)P(x,y). $$
Отсюда
$$ \boxed{ P(x,y)= \frac{1}{1-xC(x)+xyC(xy)} = \frac{2} {2+\sqrt{1-4x}-\sqrt{1-4xy}} }. $$
Вся комбинаторика скобок сжалась в одну алгебраическую функцию с двумя квадратными корнями. Но числа Фибоначчи в выводе пока почти не участвовали.
Квадратные корни здесь понимаются как формальные степенные ряды. Для $\sqrt{1-4x}$ выбирается ветвь с постоянным членом $1$: $1-2x-2x^2-4x^3-\cdots$. Поэтому не нужно обсуждать сходимость, разрезы комплексной плоскости или приближённые значения — все равенства являются равенствами коэффициентов.
Полином $P_n(y)$ можно понимать как сумму всех выражений, если вместо Фибоначчи подставить геометрическую последовательность $1,y,y^2,\ldots$. Такая замена удобна потому, что сдвиг индекса просто умножает хвост на степень $y$.
Для произвольной последовательности сдвинутый хвост $x_{k+1},x_{k+2},\ldots$ обычно становится новым объектом, зависящим от $k$. Для степеней всё иначе: $a^{k+1},a^{k+2},\ldots=a^{k+1}(1,a,a^2,\ldots)$. Именно поэтому корневое разбиение не потребовало дополнительного состояния.
Для Фибоначчи этот приём работает благодаря корням характеристического уравнения $z^2-z-1=0$:
$$ \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2},\qquad F_k=\frac{\varphi^k-\psi^k}{\sqrt5}. $$
Линейность сразу даёт
$$ \boxed{ A(n)=\frac{P_n(\varphi)-P_n(\psi)}{\sqrt5} }. $$
Поэтому производящая функция искомой последовательности равна
$$ A(x)= \frac{1}{\sqrt5} \left( \frac{2}{2+\sqrt{1-4x}-\sqrt{1-4\varphi x}} - \frac{2}{2+\sqrt{1-4x}-\sqrt{1-4\psi x}} \right). $$
Это красивый замкнутый ответ для всей последовательности. Однако красивой формулы недостаточно: нам нужен коэффициент при $x^{10^7}$, и раскрывать миллионы членов обычным умножением рядов всё ещё слишком дорого.
Здесь виден общий принцип: формула Бине диагонализует оператор сдвига. Тот же путь можно повторить для другой последовательности, заданной линейной рекуррентностью с постоянными коэффициентами, подставляя в $P(x,y)$ корни её характеристического многочлена.
Зафиксируем геометрическое основание $a$ и обозначим
$$ G_a(x)=P(x,a)= \frac{2}{2+\sqrt{1-4x}-\sqrt{1-4ax}} = \sum_{n\ge0}g_n(a)x^n. $$
Введём
$$ U=\sqrt{1-4x},\qquad V=\sqrt{1-4ax}. $$
Дважды домножая на сопряжённые выражения, получаем
Сначала домножим на $2+U+V$. Разность квадратов убирает $V$ из знаменателя:
$$ G_a(x)= \frac{2+U+V} {2\left(1+U+(a-1)x\right)}. $$
Затем домножим на $1-U+(a-1)x$. Теперь исчезает и $U$, потому что $U^2=1-4x$. После раскрытия скобок получается
$$ G_a(x)= \frac{ 1+2(a+1)x +\left(-1+(a-1)x\right)U +\left(1+(a-1)x\right)V -UV }{ 4(a+1)x+2(a-1)^2x^2 }. $$
При $x=0$ и числитель, и знаменатель обращаются в ноль. Это не полюс: исходная функция имеет $G_a(0)=1$. У числителя есть общий множитель $x$. Если назвать числитель $N_a(x)$ и положить $H_a(x)=N_a(x)/x$, то
$$ \boxed{ G_a(x)= \frac{H_a(x)} {4(a+1)+2(a-1)^2x} }. $$
После удаления устранимой особенности знаменатель стал линейным. В числителе остались только три базовых ряда: $U$, $V$ и их произведение $W=UV$.
На этом месте особенно легко принять ноль в знаменателе при $x=0$ за настоящую проблему. Но постоянный член исходного ряда известен заранее: единственное дерево с одним листом даёт $G_a(0)=1$. Значит, рационализация лишь создала общий множитель $x$, который обязан сократиться.
Пусть
$$ U(x)=\sum_{n\ge0}u_nx^n,\qquad V(x)=\sum_{n\ge0}v_nx^n,\qquad W(x)=\sum_{n\ge0}w_nx^n. $$
Из $U^2=1-4x$ после дифференцирования следует $(1-4x)U'+2U=0$. Сравнение коэффициентов даёт
$$ u_0=1,\qquad \boxed{ u_n=\frac{4n-6}{n}u_{n-1} }\quad(n\ge1). $$
Для второго корня аналогично
$$ v_0=1,\qquad \boxed{ v_n=a\frac{4n-6}{n}v_{n-1} }. $$
Наконец,
$$ W(x)^2=(1-4x)(1-4ax) =1-4(a+1)x+16ax^2. $$
Дифференцирование и сравнение коэффициентов дают рекуррентность второго порядка
Если обозначить подкоренной многочлен через $Q_a(x)=1-4(a+1)x+16ax^2$, то из $W^2=Q_a$ следует $2WW'=Q_a'$. Умножение на $W$ заменяет оставшийся корень на $W^2$:
$$ 2Q_a(x)W'(x)-Q_a'(x)W(x)=0. $$
Коэффициент при $x^{n-1}$ в этом дифференциальном уравнении и даёт следующую формулу:
$$ w_0=1,\qquad w_1=-2(a+1), $$
$$ \boxed{ w_n= \frac{ 2(a+1)(2n-3)w_{n-1} - 16a(n-3)w_{n-2} }{n} }\quad(n\ge2). $$
Запишем $H_a(x)=\sum_{n\ge0}h_n(a)x^n$. После сдвига индекса, вызванного делением $N_a(x)$ на $x$, получаем
$$ h_0(a)=4(a+1), $$
$$ \boxed{ h_n(a)= -u_{n+1}+(a-1)u_n +v_{n+1}+(a-1)v_n -w_{n+1} }\quad(n\ge1). $$
Поскольку $\left(4(a+1)+2(a-1)^2x\right)G_a(x)=H_a(x)$, коэффициенты $g_n(a)=P_n(a)$ восстанавливаются ещё одной рекуррентностью первого порядка:
$$ g_0(a)=1, $$
$$ \boxed{ g_n(a)= \frac{ h_n(a)-2(a-1)^2g_{n-1}(a) }{4(a+1)} }\quad(n\ge1). $$
На каждом шаге обновляется фиксированное число величин. Поэтому нужный коэффициент можно получить за $O(n)$ арифметических операций и $O(1)$ дополнительной памяти. Это уже подходящий масштаб для $10^7$.
Подставлять вещественные приближения $\varphi$ и $\psi$ нельзя: миллионы операций полностью разрушат точность. Вместо этого работаем сразу по модулю
$$p=10^9+9$$
в квадратичной алгебре
$$ K=\mathbb F_p[s]/(s^2-5). $$
Каждый элемент имеет вид $r+ts$, где $r,t\in\mathbb F_p$, а умножение выполняется по правилу $s^2=5$. В этой алгебре можно точно положить
$$ (r_1+t_1s)(r_2+t_2s) = (r_1r_2+5t_1t_2) +(r_1t_2+t_1r_2)s. $$
$$ \varphi=\frac{1+s}{2},\qquad \psi=\frac{1-s}{2}. $$
Сопряжение $r+ts\mapsto r-ts$ переводит $\varphi$ в $\psi$. Коэффициенты $P_n(y)$ целые, поэтому достаточно вычислить только $P_n(\varphi)$. Если
$$ P_n(\varphi)=r_n+t_ns, $$
то $P_n(\psi)=r_n-t_ns$, и формула Бине сокращается до
$$ \boxed{A(n)=2t_n\pmod p}. $$
Все деления в рекуррентностях корректны. Индексы не превосходят $10^7+1<p$, поэтому $n$ обратим по модулю $p$; число $2$ также обратимо. Наконец,
Формального элемента $s$ тоже не нужно бояться: $s^{-1}=s/5$, поскольку $s^2=5$ и $5$ обратимо по модулю $p$. Для деления на $a+1$ достаточно проверить норму этого элемента.
$$ (\varphi+1)(\psi+1) = \frac{(3+s)(3-s)}{4} = \frac{9-5}{4}=1, $$
так что знаменатель $4(a+1)$ не создаёт особого случая ни для $a=\varphi$, ни для $a=\psi$.
В этом выводе опасны не сложные теоремы, а маленькие сдвиги и знаки. Полезно отдельно проверить:
Рекуррентности воспроизводят $P_1(a)=1-a$, $P_2(a)=2-2a$ и $P_3(a)=5-5a+a^2-a^3$. После подстановки $\varphi$ они дают все три контрольных значения из условия: для $n=3$, $10$ и $100$.
Более общий теоретический фон здесь тоже хорошо виден: алгебраическая производящая функция является D-конечной, а её коэффициенты P-рекурсивны. Но выводить одну большую рекуррентность автоматическим исключением радикалов не требуется. Три коротких ряда $U,V,W$ дают гораздо прозрачнее тот же результат. Связь D-конечных функций и P-рекурсивных последовательностей подробно разобрана в работе Ричарда Стэнли Differentiably Finite Power Series.
Если смотреть только на последнюю формулу, путь к ней кажется почти неизбежным. На деле у каждого шага была своя причина:
Важный практический урок здесь в том, что компактная производящая функция ещё не завершает решение. Для индекса $10^7$ нужно сразу спрашивать, как извлечь её коэффициент без длинных свёрток и без хранения всего ряда.
Исходно требовалось просуммировать экспоненциально много выражений. Бинарные деревья превратили скобки в комбинаторный объект, чётность правых рёбер — в знаки листьев, а полином $P_n(y)$ собрал все знаки одной строки. Производящая функция убрала каталановскую свёртку, формула Бине свела Фибоначчи к двум геометрическим последовательностям, а рационализация оставила три ряда с короткими рекуррентностями.
В результате перебор $C_{10^7}$ деревьев заменяется линейным проходом по индексам в точной квадратичной алгебре.