Задача.$$$\newline$$$ Дано $$$n$$$ $$$\le$$$ $$$3 \cdot 10^{5}$$$ белых досок, длина $$$i$$$-ой $$$a_i \le 3 \cdot 10^5$$$, и $$$t$$$ $$$\le$$$ $$$5$$$ красных, длина $$$i$$$-ой $$$b_i \le 3 \cdot 10^5$$$. Поликарп хочет собрать забор из ровно одной красной и нескольких (возможно нуля) белых досок. Забор хороший, если до красной доски белые строго возрастают, после строго убывают и каждая белая строго меньше красной. Более формально пусть $$$l_1$$$, $$$l_2$$$, ..., $$$l_m$$$ длины досок, тогда должно выполняться условия:

• В заборе должна использоваться ровно одна красная доска (пусть она находится в позиции $$$j$$$);
• Для каждого $$$i \in [1, j - 1]$$$ $$$l_i \lt l_{i+1}$$$;
• Для каждого $$$i \in [j, m - 1]$$$ $$$l_i \gt l_{i+1}$$$.

Два забора считаются различными, если их массивы длин различны. Поликарп построит свой забор следующим образом: он поставит все доски слева направо на землю (высоту 0), без зазоров, то есть эти доски образуют многоугольник: $$$\newline$$$ Пример: забор с массивом длин [3,5,4,2,1]. Вторая доска — красная. Периметр этого забора равен 20.$$$\newline$$$ Поликарпу интересны заборы только $$$q \le 3 \cdot 10^{5}$$$ периметров. Требуется для каждого $$$Q_i \le 12 \cdot 10^{5}$$$(необходимый периметр), посчитать количество различных заборов периметром $$$Q_i$$$.$$$\newline$$$ Решение.$$$\newline$$$ Так как количество красных мало, зафиксируем красную доску, пусть это позиция $$$i$$$ в $$$b$$$, пусть количество белых досок равно $$$cnt$$$ и тогда периметр забора равен $$$2 \cdot (b_i + cnt + 1)$$$. Введём многочлен равный произведению следующих выражений по каждой возможной длине(путь это будет $$$l$$$) белой доски:

• Если количество вхождений $$$l$$$ в $$$a = 1$$$, домножим многочлен на $$$1 + 2x$$$ (если мы добавляем в забор доску длины $$$l$$$ то есть 2 варианта куда поставить: левее красной и правее, так же к $$$cnt$$$ добавится 1, в противном случае ничего единица на ответ не повлияет),
• Если количество вхождений $$$l$$$ в $$$a \gt 1$$$, домножим многочлен на $$$1 + 2x + x^2$$$ (теперь доску $$$l$$$ можно добавить одним способом как в первом случае и добавить с обеих сторон, что принесёт к $$$cnt$$$ 2).

В конечном итоге у нас получился многочлен $$$P(x)$$$. В таком случае ответ на $$$j$$$-ый запрос (при фиксированном $$$i$$$) равен коэффициенту в $$$P(x)$$$ при $$$x^{\frac{Q_i}{2} - b_i - 1}$$$(далее коэффициент при $$$x^k$$$, будем обозначать как $$$P(x)[x^k]$$$). Если $$$\alpha$$$ — количество вхождений первого слагаемого в $$$P(x)$$$, а $$$\beta$$$ количество вхождений второго слагаемого в $$$P(x)$$$, то $$$P(x) = (1 + 2x)^{\alpha} \cdot (1 + x)^{2\beta}$$$.$$$\newline$$$ Таким образом мы получили решение за $$$O(nt \log n)$$$, если посчитать $$$P(x)$$$ через БПФ.$$$\newline$$$ Убираем БПФ.$$$\newline$$$ Пусть $$$P(x) = f_{n}x^n + f_{n-1}x^{n-1} + ... + f_{1}x + f_0 = (1 + 2x)^{\alpha} \cdot (1 + x)^{2\beta}$$$$$$\newline$$$ $$$P'(x) = nf_{n}x^{n-1} + (n-1)f_{n-1}x^{n-2} + ... + 2f_{2}x + f_1 = \frac{2\alpha P(x)}{1 + 2x} + \frac{2\beta P(x)}{1 + x}$$$$$$\newline$$$ $$$\frac{P'(x)}{P(x)} = \frac{2(\alpha + \beta) + 2(\alpha + 2\beta)x}{1 + 3x + 2x^2} \Rightarrow P'(x) \cdot (1 + 3x + 2x^2) = P(x) \cdot (2(\alpha + \beta) + 2(\alpha + 2\beta)x)$$$$$$\newline$$$ $$$A(x) = P'(x) \cdot (1 + 3x + 2x^2)$$$$$$\newline$$$ $$$A(x)[x^k] = P'(x)[x^k] \cdot 1 + P'(x)[x^{k-1}] \cdot 3 + P'(x)[x^{k-2}] \cdot 2 = (k+1)f_{k+1} + 3kf_{k} + 2(k-1)f_{k-1}$$$$$$\newline$$$ $$$B(x) = P(x) \cdot (2(\alpha + \beta) + 2(\alpha + 2\beta)x)$$$$$$\newline$$$ $$$B(x)[x^k] = P(x)[x^k] \cdot 2(\alpha + \beta) + P(x)[x^{k-1}] \cdot 2(\alpha + 2\beta) = 2(\alpha + \beta)f_k + 2(\alpha + 2\beta)f_{k-1}$$$$$$\newline$$$ $$$A(x)[x^k] = B(x)[x^k] \Rightarrow (k+1)f_{k+1} + 3kf_{k} + 2(k-1)f_{k-1} = 2(\alpha + \beta)f_k + 2(\alpha + 2\beta)f_{k-1} \Rightarrow$$$$$$\newline$$$$$$\Rightarrow f_{k+1} = \frac{(2\alpha + 2\beta - 3k)f_k + (2\alpha + 4\beta - 2k + 2)f_{k-1}}{k+1}$$$$$$\newline$$$ В результате получили рекуррентную формулу для $$$f_k$$$, $$$f_0 = 1, f_1 = 2(\alpha + \beta)$$$. Так же надо проверить частные случаи: $$$\alpha = 0$$$ или $$$\beta = 0$$$. Теперь решение работает за $$$O(nt)$$$.$$$\newline$$$ Благодарность.$$$\newline$$$ Спасибо teraqqq, за показанный выше приём.