Обозначим через Fj(t) число представлений t первыми j разрядами с коэффициентами от 0 до C. Начинаем с F0(0)=1, F0(t)=0 при t=0. Добавляя разряд веса w, получаем F_(j+1)(t)=сумма Fj(t−uw) по целым 0≤u≤C; отрицательные аргументы дают ноль. Это разбиение на непересекающиеся случаи по новому коэффициенту.
Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.
Применение в задаче
Шаг 1. Обозначим через Fj(t) число представлений t первыми j разрядами с коэффициентами от 0 до C. Начинаем с F0(0)=1, F0(t)=0 при t=0. Добавляя разряд веса w, получаем F_(j+1)(t)=сумма Fj(t−uw) по целым 0≤u≤C; отрицательные аргументы дают ноль. Это разбиение на непересекающиеся случаи по новому коэффициенту.