Кратко: задача — число неотрицательных целых решений уравнения $x_1+\cdots +x_n=m$ при ограничениях $0\le x_i\le u_i$. Обсуждение методов и когда каждый предпочтителен.
Основные факты и формулы
- Общая формула через порождение: количество равно коэффициенту при $z^m$ в произведении
$$\prod _{i=1}^n(1+z+\cdots +z^{u_i})=\prod _{i=1}^n\frac{1-z^{u_i+1}}{1-z}.$$ - Формула включений–исключений (удобна для малых $n$):
$$\#=\sum _{S\subseteq \{\mathrm{1..}n\}}(-1{)}^{|S|}(\genfrac{}{}{0ex}{}{m-{\sum }_{i\in S}(u_i+1)+n-1}{n-1}),$$ где слагаемые с отрицательной верхней частью бинома считаются нулём.
- Спецслова:
- без верхних ограничений ($u_i=\infty$): $\left(\genfrac{}{}{0ex}{}{m+n-1}{n-1}\right)$.
- для булевых ограничений ($u_i\in \{0,1\}$): число способов — $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ (если все $u_i=1$).
Сравнение методов по параметрам
1) Динамическое программирование (DP, классический knapsack)
- Схема: DP по сумме — после i ящиков массив size $\mathrm{0..}m$.
- Сложность: примерно $O(n\cdot m)$ (с оптимизациями сдвигов/префикс-сумм можно держать те же границы).
- Память: $O(m)$.
- Когда предпочительно:
- $m$ умеренное (например до $10^6$ при хорошей оптимизации) и $n$ может быть большим.
- нужны все или многие значения для разных $m$ (таблица DP даст их сразу).
- простая реализация, точный результат, легко работать с неравными $u_i$.
- Ограничения: при очень большом $m$ (много миллионов) становится медленно/памятозатратно.
2) Породные функции и свёртки (полиномиальная умножение, FFT/NTT)
- Идея: перемножить много полиномов $P_i(z)=1+z+\cdots +z^{u_i}$ и взять коэффициент при $z^m$.
- Сложность:
- наивно $O(n\cdot m^2)$ — неприемлемо;
- с оптимальным D&C умножением и FFT/NTT — примерно $O(M\log M\log n)$, где $M$ — степень итогового полинома (порядка $\min (m,\sum u_i)$).
- Когда предпочительно:
- большие $n$ и умеренный/большой $m$, особенно если суммарная степень небольшая или распределена по небольшим $u_i$.
- нужен один коэффициент или несколько, и вы можете использовать быстрые свёртки (NTT если работа по модулю).
- многие одинаковые маленькие множители — выгодно объединять через D&C.
- Преимущества: асимптотически быстро при больших степенях; можно вычислять модульно (NTT).
- Минусы: сложнее в реализации, требует аккуратной работы с точностью/модулем и памятью.
3) Формула включений–исключений
- Сложность: $O(2^n)$ перебора подмножеств (или \(O\big(\sum_k \binom{n}{k}\)\) с отсечением), плюс вычисления биномиалов.
- Когда предпочительно:
- маленький \(n\) (обычно $n\le 20$–$25$); особенно удобно если многие $u_i$ большие (включая бесконечные) — тогда число значимых подмножеств может быть небольшим.
- если есть симметрия (все $u_i=u$): формула упрощается до суммы по $k$:
$$\#=\sum _{k=0}^{\lfloor m/(u+1)\rfloor }(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k}\left)\right(\genfrac{}{}{0ex}{}{m-k(u+1)+n-1}{n-1}).$$ - Преимущества: простая точная формула, легко получить аналитически.
- Минусы: экспоненциально растёт по $n$.
Практические рекомендации (резюме)
- Если $n$ мал (например ≤20): используйте включения–исключения (простота, часто быстрый результат).
- Если $m$ мал/умеренный и $n$ может быть большим: используйте DP $O(nm)$ (простая, экономная по памяти $O(m)$).
- Если и $n$ и $m$ большие, но индивидуальные $u_i$ небольшие или суммарная степень относительно невелика: используйте умножение полиномов + FFT/NTT (D&C свёртки).
- Если все $u_i$ равны или есть упрощения — сначала попытайтесь аналитическую формулу со включениями (сумма по $k$).
- Если нужно вычислять по модулю простого числа — реализуйте NTT для порожд. функций.
- Быстрая проверка граничных случаев: если $m>\sum u_i$ — ответ 0; если $m=\sum u_i$ — ответ 1.
Дополнительно
- Для очень больших параметров, где требуется приближение, можно рассмотреть центральную предельную аппроксимацию суммы ограниченных случайных величин, но это даёт лишь асимптотику, а не точный счёт.
Если нужно, могу: дать пример кода (DP или NTT), оценить ресурсы для конкретных чисел $m,n,u_i$ или выбрать метод для ваших конкретных входных размеров.