количество способов распространения

Question

если у нас есть n разных вещей, и нам нужно распределить их среди m разных людей, то сколько способов мы можем сделать это так, чтобы для каждого из m людей были условия, чтобы: человек 1 мог иметь по крайней мере что-то и вбольшинство b вещей, у человека 2 может быть по крайней мере c вещей и самое большее d вещей и т. д.до п, но не могу придумать эффективный алгоритм.Спасибо

Answer 1

Вы, вероятно, хотите использовать подход генерирующей функции.Представляет количество объектов, которые человек i получает по показателям x.Это означает, что если человек i может иметь по крайней мере 3 и самое большее 7 вещей, это соответствует термину

x^3 + x^4 + x^5 + x^6 + x^7

Не забудьте думать о + как OR и * как AND.Если мы хотим навязать условия и человеку 1 и человеку 2, то умножим их функции вместе.Например, если у человека 1 имеется от 3 до 7 вещей, и, скажем, у человека 2 есть по крайней мере 5 вещей, и добавьте третьего человека с не более 10 вещей.Затем мы получаем:

(x^3 + x^4 + x^5 + x^6 + x^7) * (x^5 + x^6 + ... ) * (1 + x + x^2 + ... + x^10)

, который также может быть записан как

(x^3 + x^4 + x^5 + x^6 + x^7) * ( x^5/(1+x) ) * (1 + x + x^2 + ... + x^10)

Способ получения информации из этого заключается в следующем.Коэффициент x^M в расширении этих терминов дает количество способов распределить в общей сложности M вещей среди всех людей, на которых распространяются данные ограничения.

Вы можете решить это из формулили напишите программу для извлечения коэффициента, но идея состоит в том, чтобы использовать генерирующие функции как удобный и эффективный способ кодирования ограничений вместе с ответом.