Модообразная последовательность

Посмотрим, как будет выглядеть ответ: сначала будет идти префикс вида $$$x, x + y, \ldots, x + k\cdot y$$$, а после — какое-то число блоков вида $$$x \bmod y, x \bmod y + y, \ldots, x \bmod y + k \cdot y$$$.

Мы можем вычесть из всех элементов последовательности число $$$x \bmod y$$$, а после разделить все элементы на $$$y$$$ (все элементы будут делиться на $$$y$$$, так как изначально у них был остаток $$$x \bmod y$$$). Пусть $$$b_1 = \frac{x - x \bmod y}{y}$$$. Тогда наша последовательность будет начинаться с $$$b_1, b_1 + 1, \ldots, b_1 + k_1$$$, а после будут идти блоки вида $$$0, 1, \ldots, k_i$$$.

Посчитаем такие значения: $$$dp_i$$$ — минимальная длина последовательности из блоков вида $$$0, 1, \ldots, k_j$$$, имеющая сумму $$$i$$$. Можно посчитать это значение для всех чисел от $$$0$$$ до $$$S$$$ методом динамического программирования. Если мы обработали все значения от $$$0$$$ до $$$k-1$$$, то для $$$k$$$ мы посчитали минимальную длину, и мы можем обновить значение $$$dp$$$ для $$$k + 1, k + 1 + 2, \ldots$$$ — всего $$$O(\sqrt{S})$$$ значений, не превышающих $$$S$$$. В этом же $$$dp$$$ можно сохранить, через какие значения мы пересчитывались, для восстановления ответа.

Теперь, мы можем перебрать длину первого блока вида $$$b_1, b_1 + 1, \ldots, b_1 + k_1$$$. Тогда мы знаем сумму оставшихся блоков, и с помощью предпосчитанного $$$dp$$$ узнаем, можно ли составить искомую последовательность или нет.