Binomial coefficients 3

Ясно, что можно считать, что n>=2k. Тогда понятно, что при фиксированном k последовательность C(n,k) монотонно возрастает при n>=2k. Поэтому при фиксированном k двоичным поиском можно найти минимальное n, при котором C(n,k)>=x. Ясно, что чем больше k, тем меньше будет соответствующее n. Поэтому найдя какую-то верхнюю границу для k, идем от этого k вниз до 1 пока не найдем такое k, для которого соответствующее n дает равенство C(n,k)=x. Это всегда произойдет хотя бы при k=1.

Верхнюю границу можно легко получить. Ясно, что минимальное C(n,k) при n>=2k и фиксированном k это C(2k,k). Так как это наибольший из биномиальных коэффициентов С(2k,0), С(2k,1), …, C(2k,2k), то он больше их среднего арифметического, то есть C(2k,k)>=( С(2k,0) + С(2k,1) + … + C(2k,2k)) / (2k+1) = (2^(2k)) / (2k+1) . Поэтому, например, при k=175 имеем C(2k,k) >= 2^350 / 351 > (2^10)^35 / 351 > 1024^35 / 351 > 1000^35 / 1000 = 10^102 > 10^100 >= x.

Значит, начиная с k=175, мы точно не пропустим искомое k.

В принципе можно вообще не делать никаких оценок, а сначала пройти от 1 вверх, пока C(2k,k)<=x. И найти эту оценку явно для каждого x. Так будет даже правильней.

Единственное, что надо еще сделать, чтоб это решение немного быстрее работало. Это останавливать вычисление C(n,k) при фиксированных n и k, если текущее значение уже превысило x. Так как хорошую верхнюю оценку для n при фиксированном k трудно получить, то двоичный поиск всегда будет начинаться со значений L=2k и R=x. Поэтому при больших k это соображение позволит сильно сэкономить на вычислениях.

Ну и, конечно, все здесь надо делать с длинной арифметикой.

А як можна швидко порахувати С(n,k), коли n=10^100?

1. BigInt Cnk=1
2. for i=1 to k do
3. begin
4. Cnk=Cnk * (n-i+1) //O(L * L)
5. Cnk=Cnk/i //O(L)
6. if Cnk>x then break //O(L)
7. end Где L - длина числа x. Итого будет O(L * L * k), что вполне приемлемо. И как я говорил надо ставить отсечку (строка 6)