Как быстро определить чётность C(n, k) без вычисления самого числа (теорема Куммера / правило Люка по модулю 2)?
В задаче нужно знать только, чётно ли C(n,k), для очень больших n,k (до 10^18). Считать само C(n,k) бессмысленно — оно гигантское. Есть ли способ узнать чётность по битам n и k напрямую? Слышал, что это связано с треугольником Серпинского.
2 ответа
Да, есть элегантный битовый критерий (частный случай теоремы Люка по модулю 2 / теоремы Куммера):
C(n, k) нечётно ⟺ (k & n) == k, то есть биты k являются подмножеством битов n.
Интуиция (Люка по p=2): C(n,k) mod 2 = ∏ C(n_i, k_i) по битам, где C(0,1)=0, а C(0,0)=C(1,0)=C(1,1)=1. Произведение зануляется ровно тогда, когда в каком-то разряде k_i=1, а n_i=0 — то есть бит k не «покрыт» битом n. Эквивалентно теореме Куммера: степень двойки в C(n,k) равна числу переносов при сложении k и (n−k) в двоичной системе; нет переносов ⟺ нечётно ⟺ биты не пересекаются ⟺ (k & (n−k))==0 ⟺ (k & n)==k.
// C(n,k) нечётно?
bool isOdd(long long n, long long k) {
if (k < 0 || k > n) return false; // C = 0, чётно
return (k & n) == k;
}
Сложность O(1) (одна битовая операция), работает для n,k до 2^63. Именно это правило рисует треугольник Серпинского, если в треугольнике Паскаля закрасить нечётные клетки.
Обобщение на произвольное простое p — теорема Куммера: показатель степени p в C(n,k) равен числу переносов при сложении k и n−k по основанию p. Отсюда, например, число нечётных элементов в n-й строке треугольника Паскаля равно 2^{(число единичных битов в n)} = 2^{popcount(n)}. Это частый «трюковый» подвопрос — считается одной строкой через __builtin_popcountll(n).