Игра со стопками карт

Аннотация

В задаче Project Euler 798 требуется подсчитать начальные наборы открытых карт, проигрышные для первого игрока. В колоде есть \(s\) мастей, в каждой масти лежат карты со значениями от \(1\) до \(n\). За ход разрешено накрыть открытую карту картой той же масти с большим значением. Игрок, которому некуда ходить, проигрывает.

Прямой перебор здесь бесполезен: начальных наборов \(2^{ns}\), а для каждого набора пришлось бы исследовать дерево игры. Решение строится в три содержательных этапа:

1. каждая масть рассматривается как отдельная конечная беспристрастная игра;
2. для одной масти выводится распределение начальных подмножеств по числам Шпрага—Гранди;
3. независимые масти объединяются ним-суммой, а число наборов с нулевой ним-суммой вычисляется через XOR-свёртку и быстрое преобразование Уолша—Адамара.

Самая трудная часть — не само преобразование, а точная классификация позиций одной масти. В ранних обсуждениях задачи встречается неполная формулировка этой классификации. Ниже используется исправленное условие, отдельно разбирается причина дополнительного ограничения и после этого проводится комбинаторный подсчёт.

1. Формализация условия

В одной масти имеются карты

\[ 1,2,\ldots,n. \]

Перед началом игры выбирается произвольное подмножество карт, в том числе пустое. Выбранные карты кладутся на стол лицом вверх и образуют начальные стопки высоты \(1\).

Ход выбирает:

• открытую карту \(Y\);
• ещё не использованную карту \(X\) той же масти;
• при этом \(X>Y\).

Карта \(X\) кладётся на \(Y\). После этого \(Y\) закрыта навсегда, а \(X\) становится верхней картой соответствующей стопки.

Игра конечна: каждый ход забирает из неиспользованной части колоды ровно одну карту. Правила одинаковы для обоих игроков, случайности и скрытой информации нет, а проигрывает игрок без допустимого хода. Следовательно, перед нами конечная беспристрастная игра с нормальным условием окончания.

Обозначим через \(C(n,s)\) число начальных наборов, проигрышных для первого игрока при оптимальной игре обоих участников.

2. Почему масти являются независимыми подиграми

Карта одной масти никогда не накрывает карту другой масти. Поэтому любой ход изменяет состояние ровно одной масти и не затрагивает остальные.

Полная позиция имеет вид

\[ P=P_1+P_2+\cdots+P_s, \]

где \(P_j\) — позиция внутри \(j\)-й масти, а знак \(+\) означает дизъюнктную сумму игр: игрок выбирает одну компоненту и делает ход только в ней.

Для таких игр применима теорема Шпрага—Гранди. Каждой позиции \(P\) сопоставляется неотрицательное целое число

\[ g(P)=\operatorname{mex}\{g(Q):P\to Q\}, \]

где \(\operatorname{mex}\) — наименьшее неотрицательное число, отсутствующее в заданном множестве, а \(P\to Q\) означает допустимый ход из \(P\) в \(Q\).

Для дизъюнктной суммы выполняется

\[ g(P_1+\cdots+P_s) = g(P_1)\oplus\cdots\oplus g(P_s), \]

где \(\oplus\) — побитовое исключающее «или».

Позиция проигрышна для игрока, которому предстоит ход, тогда и только тогда, когда её число Гранди равно нулю. Поэтому исходная задача эквивалентна подсчёту наборов мастей, для которых

\[ g(P_1)\oplus g(P_2)\oplus\cdots\oplus g(P_s)=0. \]

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

\[ 5\oplus5=0. \]

Сначала необходимо узнать полное распределение нимберов одной масти.

3. Каноническая модель одной масти

3.1. Почему закрытые карты можно удалить

После того как карта оказалась накрыта, она больше никогда не участвует в игре. Её числовое значение не влияет на будущие допустимые ходы. Поэтому после каждого хода закрытую карту можно мысленно удалить.

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

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

Это позволяет описывать позицию не всей историей стопок, а только относительным расположением текущих верхних карт среди ещё активных карт.

3.2. Обращение порядка

Пусть в одной масти открыты карты

\[ r_1<r_2<\cdots<r_k. \]

Введём обращённые координаты

\[ x_i=n-r_{k-i}, \qquad 0\le i<k. \]

Тогда

\[ 0\le x_0<x_1<\cdots<x_{k-1}. \]

Большая исходная карта получает меньшую обращённую координату. Поэтому требование «положить большую карту» превращается в движение влево, к меньшему числу.

Начальное подмножество одной масти однозначно задаёт подмножество множества

\[ \{0,1,\ldots,n-1\}. \]

Пустому начальному набору соответствует пустой кортеж.

3.3. Ход в обращённых координатах

Пусть текущее состояние равно

\[ X=(x_0,x_1,\ldots,x_{k-1}). \]

Выберем \(x_i\) и свободную позицию \(y\), для которой

\[ 0\le y<x_i, \qquad y\notin\{x_0,\ldots,x_{i-1}\}. \]

После хода старая верхняя карта \(x_i\) удаляется. Все координаты справа от неё уменьшаются на единицу из-за перенумерации оставшихся активных карт. Новое состояние имеет вид

\[ X' = \operatorname{sort} \bigl( x_0,\ldots,x_{i-1}, y, x_{i+1}-1,\ldots,x_{k-1}-1 \bigr). \]

Количество открытых стопок \(k\) не меняется. Терминальной является позиция

\[ (0,1,\ldots,k-1), \]

поскольку левее каждой открытой карты уже нет свободной позиции. Пустое состояние также терминально.

Такое описание удобно по двум причинам:

1. оно не хранит историю сделанных ходов;
2. начальные наборы и канонические состояния связаны взаимно однозначно.

4. Число Гранди для одной масти

4.1. Две характеристики позиции

Рассмотрим непустое состояние

\[ X=(x_0,\ldots,x_{k-1}). \]

Определим

\[ d=x_{k-1}-(k-1). \]

В отрезке от \(0\) до \(x_{k-1}\) находится \(x_{k-1}+1\) позиций и \(k\) открытых карт. Поэтому \(d\) — количество свободных позиций среди них.

Теперь найдём последний индекс, в котором чётность отличается от чётности крайней правой координаты:

\[ j = \max\{i<k-1:x_i\not\equiv x_{k-1}\pmod 2\}. \]

Если такого индекса нет, положим \(h=+\infty\). Иначе положим

\[ h=x_{k-1}-x_j. \]

Поскольку \(x_j\) и \(x_{k-1}\) имеют разную чётность, конечное \(h\) всегда нечётно.

4.2. Исправленная формула

Для непустой позиции её число Гранди равно

\[ \boxed{ g(X) = \max \left\{ q\ge0: q\le d,\; q\le h,\; q\equiv d\pmod2 \right\}. } \]

Для пустой позиции

\[ g(\varnothing)=0. \]

Если все \(x_i\) имеют ту же чётность, что и \(x_{k-1}\), то \(h=+\infty\) и формула упрощается:

\[ g(X)=d=x_{k-1}-(k-1). \]

Если координата противоположной чётности существует, то \(h\) ограничивает возможный нимбер, но ограничение

\[ g(X)\le d \]

сохраняется. Его нельзя выбрасывать.

Например, для

\[ X=(0,1,3) \]

получаем

\[ d=3-2=1,\qquad j=0,\qquad h=3. \]

Следовательно,

\[ g(X)=1. \]

Если оставить только условие \(g\le h\) и условие на чётность, можно ошибочно получить \(3\). Именно такой тип позиции показывает, почему ранняя краткая формулировка из обсуждения задачи нуждается в дополнительной границе \(g\le d\).

4.3. Та же формула в исходной нумерации

Для комбинаторного подсчёта удобнее вернуться к обычному порядку карт.

Пусть среди активных карт минимальная открытая карта имеет значение \(a\). Обозначим через \(d\) число неоткрытых карт в интервале

\[ \{a,a+1,\ldots,m\}, \]

где \(m\) — текущее число активных карт. Сама карта \(a\) открыта, поэтому эквивалентно можно считать пропуски только выше неё.

Пусть

\[ h = \min\{r\ge1:r\text{ нечётно и }a+r\text{ открыта}\}, \]

а при отсутствии такой карты \(h=+\infty\).

Тогда

\[ g = \max \left\{ q\ge0: q\le d,\; q\le h,\; q\equiv d\pmod2 \right\}. \]

Эквивалентная формулировка не использует \(h\):

\[ \boxed{ g = \max \left\{ q: 0\le q\le d,\; q\equiv d\pmod2,\; \{a+r:1\le r<q,\ r\text{ нечётно}\} \cap V =\varnothing \right\}, } \]

где \(V\) — множество открытых карт.

Иными словами, возможные кандидаты имеют ту же чётность, что и число пропусков \(d\). Кандидат \(q\) допустим, пока среди нечётных смещений

\[ 1,3,5,\ldots,q-1 \]

не встретилась открытая карта.

4.4. Почему формула действительно задаёт mex

Доказательство проводится индукцией по числу активных карт. После каждого хода оно уменьшается, поэтому все позиции-потомки меньше исходной в параметре индукции.

Рассмотрим позицию с минимальной открытой картой \(a\), числом пропусков \(d\) и первым нечётным открытым смещением \(h\).

Если игрок накрывает открытую карту \(y>a\), минимальная открытая карта остаётся равной \(a\). Одна отсутствовавшая карта становится открытой, а накрытая карта удаляется из активного порядка. Поэтому

\[ d'=d-1. \]

Чётность числа пропусков меняется. Такие ходы создают потомков с нимберами чётности, противоположной \(d\).

Если игрок накрывает минимальную открытую карту \(a\), пусть \(b\) — новая минимальная открытая карта до перенумерации, а

\[ t=b-a. \]

Карты между \(a\) и \(b\) больше не влияют на игру, и после перенумерации

\[ d'=d-t. \]

Эти ходы позволяют переходить между кандидатами той же чётности, пропуская начальный участок позиции.

Остаётся проследить, когда такая последовательность переходов блокируется. До первого открытого нечётного смещения \(h\) все нечётные места свободны. Поэтому для каждого

\[ 0\le r<g(X) \]

можно выбрать ход одного из двух описанных типов так, чтобы у потомка выполнялось

\[ g(X')=r. \]

Чётность \(r\), отличная от чётности \(d\), достигается ходом, не меняющим минимум \(a\); совпадающая чётность достигается ходом из минимальной карты. При движении вправо по возможным значениям эта конструкция заканчивается ровно в одной из двух точек:

• исчерпаны все \(d\) пропусков;
• встретилась первая открытая карта на нечётном смещении \(h\).

Поэтому верхний достижимый кандидат ограничен одновременно числами \(d\) и \(h\).

Обратное утверждение проверяется теми же двумя типами ходов. Ход выше минимума меняет чётность \(d\), а ход из минимума либо уменьшает допустимую границу, либо переносит первый нечётный блокирующий элемент левее. Ни один ход не оставляет потомку одновременно:

\[ q\equiv d\pmod2,\qquad q\le d,\qquad q\le h \]

при \(q=g(X)\).

Следовательно,

\[ \{0,1,\ldots,g(X)-1\} \subseteq \{g(X'):X\to X'\}, \]

но

\[ g(X)\notin\{g(X'):X\to X'\}. \]

По определению минимального исключённого значения это и означает

\[ g(X) = \operatorname{mex}\{g(X'):X\to X'\}. \]

Содержательно формула говорит следующее: почти весь нимбер определяется числом свободных мест \(d\), а первая открытая карта на нечётном расстоянии от минимума может преждевременно оборвать последовательность достижимых значений.

На небольшой колоде этот переход удобно проверить напрямую. Можно выбрать открытые карты, посмотреть канонические координаты и нимберы всех допустимых потомков. Следующие вкладки показывают, как частоты нимберов объединяются XOR-свёрткой и проходят через преобразование Уолша—Адамара.

5. Распределение нимберов одной масти

Обозначим через

\[ F_N(v) \]

число подмножеств карт одной масти из \(N\) карт, имеющих число Гранди \(v\).

Всего подмножеств \(2^N\), поэтому обязательна контрольная сумма

\[ \sum_{v\ge0}F_N(v)=2^N. \]

Максимально возможный нимбер равен \(N-1\), следовательно,

\[ F_N(v)=0 \qquad\text{при }v\ge N. \]

5.1. Параметризация по минимальной открытой карте

Рассмотрим непустое начальное подмножество. Пусть \(a\) — его минимальная карта и

\[ L=N-a \]

— число карт выше неё.

Каждое такое подмножество однозначно задаётся множеством отсутствующих смещений

\[ H\subseteq\{1,2,\ldots,L\}. \]

Положим

\[ d=|H|. \]

По классификации из предыдущего раздела нимбер зависит от:

• чётности \(d\);
• наличия в \(H\) начальных нечётных смещений;
• первого нечётного смещения, которое не входит в \(H\), то есть соответствует открытой карте.

Это превращает задачу из анализа дерева игры в обычный подсчёт подмножеств.

6. Число позиций с нимбером ноль

Сначала рассмотрим \(v=0\).

Пустое начальное подмножество даёт одну проигрышную позицию.

Для непустого подмножества нимбер равен нулю в двух случаях.

6.1. Пропусков нет

Если

\[ d=0, \]

то вместе с минимальной картой \(a\) открыты все карты от \(a\) до \(N\). Для каждого \(a\) существует ровно одно такое подмножество. Всего их \(N\).

6.2. Есть положительное чётное число пропусков

Если \(d\ge2\) чётно, следующий кандидат после нуля равен \(2\). Чтобы он был заблокирован, карта \(a+1\) должна быть открыта.

После фиксации \(a\) и \(d\) отсутствующие карты выбираются среди остальных \(L-1\) смещений:

\[ \binom{L-1}{d}. \]

Поэтому при \(N\ge2\)

\[ F_N(0) = 1+N + \sum_{\substack{d\ge2\\d\text{ чётно}}} \sum_{L=d}^{N-1} \binom{L-1}{d}. \]

Используем «клюшечную» биномиальную формулу

\[ \sum_{L=d}^{N-1}\binom{L-1}{d} = \binom{N-1}{d+1}. \]

Тогда

\[ F_N(0) = 1+N + \sum_{\substack{j\ge3\\j\text{ нечётно}}} \binom{N-1}{j}. \]

Сумма биномиальных коэффициентов с нечётными индексами равна половине полной суммы строки:

\[ \sum_{\substack{j\ge0\\j\text{ нечётно}}} \binom{N-1}{j} = 2^{N-2}. \]

Из неё нужно удалить член

\[ \binom{N-1}{1}=N-1. \]

В результате

\[ \boxed{ F_N(0)=2^{N-2}+2 } \qquad(N\ge2). \]

При \(N=1\) оба подмножества — пустое и состоящее из единственной карты — терминальны, поэтому

\[ F_1(0)=2. \]

7. Положительные нимберы

Для \(k\ge1\) отдельно выпишем чётные и нечётные значения.

7.1. Чётный нимбер \(v=2k\)

Чтобы нимбер был равен \(2k\), необходимо:

1. \(d\) чётно;

2. \(d\ge2k\);

3. смещения

   \[ 1,3,\ldots,2k-1 \]

   отсутствуют, то есть входят в \(H\);

4. если \(d>2k\), то смещение \(2k+1\) должно присутствовать среди открытых карт, иначе был бы допустим следующий кандидат \(2k+2\).

Первые \(k\) нечётных смещений принудительно отсутствуют.

Если \(d=2k\), остаётся выбрать ещё \(k\) отсутствующих смещений среди \(L-k\) свободно выбираемых мест:

\[ \binom{L-k}{k}. \]

Если \(d\ge2k+2\), смещение \(2k+1\) принудительно открыто. После учёта \(k\) принудительных пропусков и одной принудительно открытой позиции остаётся

\[ \binom{L-k-1}{d-k} \]

вариантов.

Суммирование сначала по \(L\), затем по допустимым \(d\), даёт удобную форму. Положим

\[ R=N-k-2. \]

После применения клюшечной формулы получаем

\[ F_N(2k) = \binom{R+2}{k+1} + \sum_{\substack{q=k+2\\q\equiv k\pmod2}}^R \binom{R+1}{q+1}. \]

Заменим \(j=q+1\):

\[ F_N(2k) = \binom{R+2}{k+1} + \sum_{\substack{j=k+3\\j\equiv k+1\pmod2}}^{R+1} \binom{R+1}{j}. \]

Сумма коэффициентов заданной чётности в строке \(R+1\) равна \(2^R\). Поэтому

\[ F_N(2k) = 2^R + \binom{R+2}{k+1} - \sum_{\substack{0\le j\le k+1\\j\equiv k+1\pmod2}} \binom{R+1}{j}. \]

По формуле Паскаля

\[ \binom{R+1}{j} = \binom{R}{j} + \binom{R}{j-1}. \]

В последней сумме первый член покрывает индексы одной чётности, второй — индексы другой. Вместе они покрывают все индексы от \(0\) до \(k+1\) ровно по одному разу:

\[ \sum_{\substack{0\le j\le k+1\\j\equiv k+1\pmod2}} \binom{R+1}{j} = \sum_{i=0}^{k+1}\binom{R}{i}. \]

Кроме того,

\[ \binom{R+2}{k+1} = \binom{R}{k-1} +2\binom{R}{k} +\binom{R}{k+1}. \]

После сокращения остаётся

\[ \boxed{ F_N(2k) = 2^{N-k-2} + \binom{N-k-2}{k} - \sum_{i=0}^{k-2} \binom{N-k-2}{i}. } \]

7.2. Нечётный нимбер \(v=2k-1\)

Теперь чётность \(d\) нечётна.

Для кандидата \(2k-1\) должны отсутствовать нечётные смещения

\[ 1,3,\ldots,2k-3. \]

Их \(k-1\).

Если

\[ d=2k-1, \]

граница по числу пропусков сама останавливает рост нимбера.

Если

\[ d\ge2k+1, \]

смещение \(2k-1\) должно соответствовать открытой карте, иначе был бы допустим кандидат \(2k+1\).

Подсчёт полностью повторяет чётный случай, но теперь

\[ R=N-k-1. \]

В результате

\[ \boxed{ F_N(2k-1) = 2^{N-k-1} + \binom{N-k-1}{k} - \sum_{i=0}^{k-2} \binom{N-k-1}{i}. } \]

7.3. Единая запись

Для положительного нимбера \(v\) положим

\[ k=\left\lceil\frac v2\right\rceil \]

и

\[ R_v = N-k-1-\mathbf 1_{\{v\text{ чётно}\}}. \]

Тогда

\[ \boxed{ F_N(v) = 2^{R_v} + \binom{R_v}{k} - \sum_{i=0}^{k-2}\binom{R_v}{i}, \qquad v>0. } \]

Здесь используется стандартное соглашение

\[ \binom ab=0 \]

при \(b<0\) или \(b>a\), а сумма с верхней границей меньше нижней считается пустой.

Биномиальные тождества, использованные в выводе, собраны, например, в разделе 26.3 Digital Library of Mathematical Functions.

8. Проверка формул на малых \(N\)

Для первых значений \(N\) распределения имеют вид:

\(N\)	\((F_N(0),F_N(1),\ldots,F_N(N-1))\)	Сумма
\(1\)	\((2)\)	\(2\)
\(2\)	\((3,1)\)	\(4\)
\(3\)	\((4,3,1)\)	\(8\)
\(4\)	\((6,6,3,1)\)	\(16\)
\(5\)	\((10,11,6,4,1)\)	\(32\)
\(6\)	\((18,20,11,10,4,1)\)	\(64\)

В каждой строке сумма равна \(2^N\), как и должна.

Для \(N\le12\) можно независимо:

1. перебрать все \(2^N\) начальных подмножеств;
2. рекурсивно вычислить mex для каждого канонического состояния;
3. сравнить полученные нимберы с исправленной формулой;
4. сравнить частоты с биномиальными выражениями.

Все четыре проверки дают одинаковые распределения.

9. Как вычислить все частоты за линейное время

Закрытые формулы ещё не означают быстрый алгоритм. Если для каждого \(k\) отдельно считать сумму

\[ \sum_{i=0}^{k-2}\binom{N-k-2}{i}, \]

общая сложность станет квадратичной.

Нужно использовать связь соседних биномиальных хвостов.

9.1. Суммы для чётных нимберов

Определим

\[ A_k = \sum_{i=0}^{k-2} \binom{N-k-2}{i}. \]

Положим

\[ R_k=N-k-2. \]

Тогда

\[ A_k = \sum_{i=0}^{k-2}\binom{R_k}{i}. \]

Для предыдущего индекса

\[ A_{k-1} = \sum_{i=0}^{k-3}\binom{R_k+1}{i}. \]

Применим формулу Паскаля:

\[ \begin{aligned} A_{k-1} &= \sum_{i=0}^{k-3} \left( \binom{R_k}{i} + \binom{R_k}{i-1} \right)\\ &= 2\sum_{i=0}^{k-3}\binom{R_k}{i} - \binom{R_k}{k-3}. \end{aligned} \]

Так как

\[ A_k = \sum_{i=0}^{k-3}\binom{R_k}{i} + \binom{R_k}{k-2}, \]

получаем рекуррентность

\[ \boxed{ 2A_k = A_{k-1} +2\binom{N-k-2}{k-2} +\binom{N-k-2}{k-3}. } \]

Начальное значение:

\[ A_1=0. \]

9.2. Суммы для нечётных нимберов

Определим

\[ B_k = \sum_{i=0}^{k-2} \binom{N-k-1}{i}. \]

Снова применяя формулу Паскаля, получаем

\[ \begin{aligned} B_k &= \sum_{i=0}^{k-2} \left( \binom{N-k-2}{i} + \binom{N-k-2}{i-1} \right)\\ &= 2A_k-\binom{N-k-2}{k-2}. \end{aligned} \]

Следовательно,

\[ \boxed{ B_k = 2A_k-\binom{N-k-2}{k-2}. } \]

После обновления одного значения \(A_k\) обе частоты вычисляются за постоянное число арифметических операций:

\[ F_N(2k) = 2^{N-k-2} + \binom{N-k-2}{k} - A_k, \]

\[ F_N(2k-1) = 2^{N-k-1} + \binom{N-k-1}{k} - B_k. \]

9.3. Вычисления по модулю

Пусть

\[ p=1\,000\,000\,007. \]

Это простое число, а в задаче

\[ N<p. \]

Поэтому биномиальные коэффициенты можно вычислять как

\[ \binom ab \equiv a!\,(b!)^{-1}\,((a-b)!)^{-1} \pmod p. \]

Факториалы и обратные факториалы предварительно считаются за \(O(N)\) времени. Деление на \(2\) в рекуррентности для \(A_k\) заменяется умножением на

\[ 2^{-1}\equiv\frac{p+1}{2}\pmod p. \]

Степени двойки также обновляются за \(O(1)\):

\[ 2^{r-1}\equiv2^r\cdot2^{-1}\pmod p. \]

В результате весь массив

\[ f_v=F_N(v), \qquad 0\le v<N, \]

строится за \(O(N)\) времени.

10. От одной масти к \(s\) мастям

Пусть

\[ f=(f_0,f_1,\ldots) \]

— распределение нимберов одной масти.

Для двух мастей число пар с общей ним-суммой \(z\) равно

\[ (f*_{\oplus}f)_z = \sum_{x\oplus y=z}f_xf_y. \]

Операция \(*_{\oplus}\) называется XOR-свёрткой.

Для \(s\) мастей требуется \(s\)-я XOR-свёрточная степень:

\[ f^{*_{\oplus}s}. \]

Искомое число проигрышных начальных наборов — её нулевая компонента:

\[ C(N,s) = \left(f^{*_{\oplus}s}\right)_0. \]

Прямое вычисление одной XOR-свёртки требует квадратичного времени. При \(N=10^7\) это неприемлемо.

11. Преобразование Уолша—Адамара

11.1. Дополнение до степени двойки

Выберем

\[ L=2^\ell\ge N \]

— минимальную степень двойки, не меньшую \(N\).

Массив частот дополняется нулями:

\[ f_v=0, \qquad N\le v<L. \]

Индексы от \(0\) до \(L-1\) рассматриваются как элементы группы

\[ (\mathbb Z/2\mathbb Z)^\ell. \]

Групповая операция в ней — побитовый XOR.

11.2. Характеры булевой группы

Для индексов \(t\) и \(x\) определим

\[ \chi_t(x) = (-1)^{\operatorname{popcount}(t\mathbin{\&}x)}. \]

Здесь \(\operatorname{popcount}\) — число единичных битов.

Преобразование Уолша—Адамара задаётся формулой

\[ \widehat f(t) = \sum_{x=0}^{L-1} f(x)\chi_t(x). \]

Это дискретное преобразование Фурье на булевой группе. Его матрица состоит только из \(1\) и \(-1\) и удовлетворяет

\[ H_L^2=L I. \]

Следовательно, обратное преобразование имеет вид

\[ f = L^{-1}H_L\widehat f. \]

Подробнее определение и рекурсивное устройство матрицы приведены в статье о преобразовании Адамара.

11.3. Почему XOR-свёртка превращается в произведение

Пусть

\[ c=a*_{\oplus}b. \]

Тогда

\[ c(z) = \sum_{x\oplus y=z}a(x)b(y). \]

Преобразуем:

\[ \begin{aligned} \widehat c(t) &= \sum_z c(z)\chi_t(z)\\ &= \sum_x\sum_y a(x)b(y)\chi_t(x\oplus y). \end{aligned} \]

Для характеров булевой группы

\[ \chi_t(x\oplus y) = \chi_t(x)\chi_t(y). \]

Поэтому

\[ \begin{aligned} \widehat c(t) &= \left(\sum_xa(x)\chi_t(x)\right) \left(\sum_yb(y)\chi_t(y)\right)\\ &= \widehat a(t)\widehat b(t). \end{aligned} \]

Значит,

\[ \widehat{f^{*_{\oplus}s}}(t) = \widehat f(t)^s. \]

11.4. Нужна только нулевая компонента

Полное обратное преобразование выполнять не требуется. Для \(x=0\)

\[ \chi_t(0)=1 \]

при любом \(t\). Поэтому

\[ \boxed{ C(N,s) \equiv L^{-1} \sum_{t=0}^{L-1} \widehat f(t)^s \pmod p. } \]

Это окончательная вычислительная формула.

Она особенно удобна потому, что после прямого преобразования достаточно:

1. возвести каждый преобразованный коэффициент в степень \(s\) по модулю \(p\);
2. сложить результаты;
3. умножить сумму на \(L^{-1}\pmod p\).

Обратный проход преобразования не нужен.

11.5. Быстрое преобразование

Рекурсивная структура матрицы Адамара использует блок

\[ \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix}. \]

На каждом уровне пары значений

\[ (u,v) \]

заменяются на

\[ (u+v,u-v). \]

Всего уровней \(\ell=\log_2L\), на каждом обрабатываются \(L\) элементов. Поэтому сложность равна

\[ O(L\log L), \]

а дополнительная память сверх самого массива может быть постоянной.

Все сложения и вычитания выполняются по модулю \(p\). Отрицательные остатки нужно нормализовать в диапазон

\[ 0,1,\ldots,p-1. \]

12. Полный алгоритм

Вычислительная схема выглядит так.

1. Построить частоты \(F_N(v)\) для \(0\le v<N\).

2. Проверить контрольную сумму

   \[ \sum_{v=0}^{N-1}F_N(v)\equiv2^N\pmod p. \]

3. Выбрать минимальную степень двойки \(L\ge N\).

4. Дополнить массив частот нулями до длины \(L\).

5. Выполнить прямое быстрое преобразование Уолша—Адамара.

6. Для каждого преобразованного коэффициента вычислить

   \[ \widehat f(t)^s\bmod p. \]

7. Сложить степени и умножить сумму на

   \[ L^{-1}\bmod p. \]

Полученное значение является \(C(N,s)\bmod p\).

13. Оценка сложности

Построение распределения одной масти занимает

\[ O(N) \]

арифметических операций.

Преобразование Уолша—Адамара занимает

\[ O(L\log L). \]

Возведение всех коэффициентов в степень бинарным методом требует

\[ O(L\log s). \]

Поскольку минимальная степень двойки удовлетворяет

\[ N\le L<2N, \]

общая сложность равна

\[ \boxed{ O(N\log N+N\log s). } \]

При \(N=s\) её можно записать как

\[ O(N\log N). \]

Память определяется массивом длины \(L\) и таблицами для биномиальных коэффициентов:

\[ O(N). \]

14. Проверка на примерах из условия

14.1. Случай \(C(3,2)\)

Для одной масти из трёх карт

\[ (F_3(0),F_3(1),F_3(2)) =(4,3,1). \]

При двух мастях XOR равен нулю тогда и только тогда, когда нимберы мастей совпадают. Поэтому

\[ C(3,2) = 4^2+3^2+1^2 = 26. \]

Это совпадает с первым примером из условия.

14.2. Случай \(C(13,4)\)

Для \(N=13\) строится массив из тринадцати ненулевых частот, после чего он дополняется до длины

\[ L=16. \]

Четвёртая XOR-свёрточная степень, вычисленная через преобразование Уолша—Адамара, даёт опубликованный в условии остаток

\[ C(13,4)\equiv540318329\pmod{1\,000\,000\,007}. \]

14.3. Основной набор параметров

Для основного случая

\[ N=s=10^7 \]

используется длина

\[ L=2^{24}=16\,777\,216. \]

Независимый расчёт прошёл следующие проверки:

• формула нимбера сравнена с рекурсивным mex на всех подмножествах при малых \(N\);
• закрытые формулы частот сравнены с полным перебором;
• сумма частот проверена против \(2^N\);
• обычная динамика XOR-свёртки для малых \(N\) и \(s\) сравнена с преобразованием;
• оба открытых примера из условия воспроизведены.

15. Ошибочные и слишком медленные подходы

15.1. Перебирать начальные наборы

Число наборов равно

\[ 2^{Ns}. \]

Даже для одной масти при \(N=10^7\) перебор невозможен.

15.2. Считать только выигрышные и проигрышные состояния одной масти

Одного бита «выигрыш/проигрыш» недостаточно. При сложении мастей нужен полный нимбер, поскольку условие общей проигрышности имеет вид

\[ g_1\oplus\cdots\oplus g_s=0. \]

15.3. Предполагать фиксированную чётность числа ходов

Длина партии зависит от выбора карт. Разные ходы могут закрывать возможность использования разных частей колоды, поэтому исход не определяется простой чётностью количества ещё доступных карт.

15.4. Использовать неполную формулу нимбера

Ограничения первым нечётным блокирующим смещением недостаточно. Обязательно сохраняется граница

\[ g\le d. \]

Позиция \((0,1,3)\) является короткой проверкой этого условия.

15.5. Считать каждый биномиальный хвост отдельно

Формула частоты содержит сумму

\[ \sum_{i=0}^{k-2}\binom{R}{i}. \]

Её повторный подсчёт для каждого \(k\) приводит к \(O(N^2)\). Линейная рекуррентность между соседними хвостами является обязательной частью решения.

15.6. Использовать обычную свёртку

Обычная свёртка соответствует сложению индексов:

\[ x+y=z. \]

Здесь индексы объединяются операцией

\[ x\oplus y=z. \]

Поэтому обычное дискретное преобразование Фурье не диагонализует нужную операцию. Требуется преобразование Фурье на булевой группе, то есть преобразование Уолша—Адамара.

15.7. Не дополнять массив до степени двойки

Нимберы лежат в диапазоне \(0,\ldots,N-1\), но XOR двух таких чисел может иметь индекс, не меньший \(N\). Пространство индексов должно быть замкнуто относительно XOR. Поэтому длина массива выбирается равной степени двойки \(L\ge N\).

15.8. Выполнять полное обратное преобразование

Задаче нужна только компонента с индексом \(0\). Для неё все характеры равны единице, поэтому достаточно усреднить возведённые в степень преобразованные коэффициенты. Обратное преобразование целого массива добавило бы ещё один проход \(O(L\log L)\) без пользы.

16. Итог

Основная цепочка преобразований выглядит так:

\[ \text{карточная игра} \longrightarrow \text{независимые масти} \longrightarrow \text{числа Шпрага—Гранди} \longrightarrow \text{биномиальное распределение одной масти} \longrightarrow \text{XOR-свёртка} \longrightarrow \text{преобразование Уолша—Адамара}. \]

Ключевой результат для одной масти — точная частота каждого положительного нимбера:

\[ F_N(v) = 2^{R_v} + \binom{R_v}{\lceil v/2\rceil} - \sum_{i=0}^{\lceil v/2\rceil-2} \binom{R_v}{i}, \]

где

\[ R_v = N-\left\lceil\frac v2\right\rceil-1 -\mathbf 1_{\{v\text{ чётно}\}}. \]

Для нулевого нимбера

\[ F_N(0)=2^{N-2}+2 \qquad(N\ge2). \]

После построения частот число проигрышных наборов для \(s\) мастей выражается одной формулой:

\[ C(N,s) \equiv L^{-1} \sum_{t=0}^{L-1} \widehat f(t)^s \pmod{1\,000\,000\,007}. \]

Таким образом, задача с астрономическим числом начальных состояний сводится к линейному построению массива и одному преобразованию размера ближайшей степени двойки.