Коротко опишу модель и три подхода + рекомендации по выбору.
Модель (расписать по непересекающимся типам для простоты подсчёта):
- пусть $a$ = число женщин-студентов, $b$ = женщин-нестудентов, $c$ = мужчин-студентов, $d$ = мужчин-не студентов. Тогда $a+b+c+d=N$. Обозначим выборы из типа через соответствующие числа $x_1,x_2,x_3,x_4$.
1) Прямая комбинаторная сумма (перебор по 4 группам)
- Полный явный подсчёт:
$$\sum _{{\begin{array}{c}{x}_1=0\end{array}}^a{\sum }_{x_2=0}^b{\sum }_{x_3=0}^c{\sum }_{x_4=0}^d}{1}_{x_1+x_2+x_3+x_4=10}{1}_{x_1+x_2\ge 3}{1}_{x_1+x_3\le 2}\left(\genfrac{}{}{0ex}{}{a}{x_1}\right)\left(\genfrac{}{}{0ex}{}{b}{x_2}\right)\left(\genfrac{}{}{0ex}{}{c}{x_3}\right)\left(\genfrac{}{}{0ex}{}{d}{x_4}\right).$$ - Когда применять: удобно если $a,b,c,d$ невелики или если ограничения маленькие (например максимум студентов =2 и комитет =10) — перебор по допустимым $x_i$ малоэффективен только при больших группах. Наименьшая реализация — ограничить суммы пределами $\min (\text{размер},10)$ и по студентам до 2.
2) Динамическое программирование (DP)
- Состояние: $DP[g][k][w][s]$ = число способов, рассматривая первые $g$ групп, выбрать $k$ человек с $w$ женщинами и $s$ студентами. Переход при добавлении группы размера $G$ (с параметрами: вклад в women и students):
$$D{P}^{\prime }[k+t][w+{\delta }_{w}t][s+{\delta }_{s}t]+=DP[k][w][s]\cdot \left(\genfrac{}{}{0ex}{}{G}{t}\right)(t=0\dots \min (G,10-k)),$$ где ${\delta }_w,{\delta }_s\in \{0,1\}$ для данной группы.
- Итог: ответ = сумма $DP[4][10][w][s]$ по $w\ge 3,s\le 2$.
- Сложность: примерно $O(\text{число групп}\times 10\times W_{\max }\times S_{\max }\times T)$, где $W_{\max }\le 10,S_{\max }\le 2,T$ — максим$t$ (обычно $\le 10$). На практике очень быстро, компактная память.
- Когда применять: универсально и стабильно при любых размерах групп, особенно если комитет небольшой (10) и верхние границы по женщинам/студентам малы — DP очень эффективен.
3) Порождающие функции (генераторы)
- Ввести три переменные: $x$ — размер комитета, $y$ — число женщин, $z$ — число студентов. ГФ по группам:
$$G(x,y,z)=\prod _{\text{группы}}\sum _{t=0}^{\text{size}}\left(\genfrac{}{}{0ex}{}{\text{size}}{t}\right)x^t{y}^{{\delta }_{w}t}{z}^{{\delta }_{s}t}.$$ В нашем разбиении:
$$G=(\sum _{t=0}^a(\genfrac{}{}{0ex}{}{a}{t})(xyz{)}^t)(\sum _{t=0}^b\left(\genfrac{}{}{0ex}{}{b}{t}\right)(xy{)}^t)(\sum _{t=0}^c(\genfrac{}{}{0ex}{}{c}{t})(xz{)}^t)(\sum _{t=0}^d\left(\genfrac{}{}{0ex}{}{d}{t}\right)x^t).$$ - Нужный ответ = сумма коэффициентов при $x^{10}$ и при $y^i{z}^j$ для $i\ge 3,j\le 2$:
$$\sum _{i=3}^{10}\sum _{j=0}^2[x^{10}{y}^i{z}^j]G(x,y,z).$$ - Когда применять: очень выгодно при больших $a,b,c,d$ и/или при необходимости ответов для многих параметров (много запросов), т.к. свёртки можно делать с помощью быстрых алгоритмов (FFT). Также наглядна теоретически (коэффициенты, асимптотика). Минус — реализация сложнее и потенциальные численные/памятные проблемы при больших степенях.
Рекомендации по выбору метода в зависимости от размеров исходного множества:
- N и группы малы (все <100, комитет =10, ограничения малы): DP или прямой перебор по 4‑группам — проще и быстро.
- N большие, но пороги ограничены малыми константами (например "не более 2 студентов", "не менее 3 женщин"): DP по суммам (ограничивая w до 10, s до 2) остаётся предпочтительным — независимость от N (работа с биномиальными коэффициентами).
- N очень большие и/или нужно много разных запросов (разные размеры комитетов, разные пороги): генераторы + быстрые свёртки (FFT) — асимптотически лучше.
- Если хочется простого аналитического выражения и порог очень маленький (например вычитать случаи с 0,1,2 женщин) — можно применять принцип включения‑исключения по малому порогу женщин; но из-за перекрытия со студентами лучше сочетать PIE с разбиением по типам (четко, но громоздко).
Если нужно, могу расписать конкретную формулу/реализацию для заданных чисел $a,b,c,d$ или дать код‑скелет DP/свёртки.