Алдымен \(a\) массивінің ұзындығын табайық. \(a\) массивінің ұзындығы \(M\)-ға тең болсын. \(M\) мәні \(15\)-тен аспайтынын байқауға болады.

Енді әр битті бөлек қарастырайық. Егер \(i\)-ші бит массивте \(c_i\) рет кездессе, онда ол массивтің соңғы \(c_i\) сандарында ғана болады. Яғни, \(a\) массивін \(c\) массиві ретінде көрсетуге болады. Мұнда \(c_i\) мәні \(i\)-ші биттің кездесу санына тең. \(c\) массиві үшін келесі шарттар орындалуы керек:

• \(\sum_{i=0}^{M-1} c_i \cdot 2^{i} = n\)

• \(c\) массивінде \(1\) мен \(M\) аралығындағы барлық мәндер болуы керек. Әйтпесе, \(c\) массивінен \(a\) массивін құрастырсақ, онда бірдей сандар болады.

Соңғы есепті \(dp_{sum,mask}\) көмегімен шешуге болады. Мұндағы \(sum\) – қалдық сомасы, \(mask\) – \(c\) массивінде бар мәндердің маскасы. \(dp_{n,0}=1\). \(c_0\) мәнін \(0\)-ден \(M\)-ға дейін сұрыптайық. \(c_0=i\) болсын. \(dp_{(sum-i)/2,mask|2^i}\) күйіне көшеміз. Жауап \(dp_{0,fullmask}\) ішінде болады. Мұнда \(fullmask\) – алғашқы \(M\) биттерінің толық маскасы болып табылады.

Жетуге болатын \(sum\) мәндерінің саны \(\log_2 n^2\)-ден аспайтынын түсінуге болады. \(dp\) мәндері \(M\)-ға тәуелді болмағандықтан, оны бір рет есептеуге болады. Орындалу уақыты: \(O(n \cdot \log_2 n^3)\).

Для начала зафиксируем длину массива \(a\). Пусть длина массива \(a\) будет равна \(M\). Можно заметить, что \(M\) будет не больше \(15\).

Теперь посмотрим на каждый бит отдельно. Если бит под номером \(i\) присутствует в массиве в \(c_i\) числах, то он присутствует только в последних \(c_i\) числах массива. То есть массив \(a\) можно представить в виде массива \(c\), где \(c_i\) равно количеству вхождении \(i\)-го бита. Для массива \(c\) должны выполняться следующие условия:

• \(\sum_{i=0}^{M-1} c_i \cdot 2^{i} = n\)

• В массиве \(c\) должны встретиться все значения от \(1\) до \(M\). Иначе, если по массиву \(c\) построить массив \(a\), то там будут одинаковые числа.

Последнюю задачу можно решить с помощью \(dp_{sum,mask}\), где \(sum\) – остаточная сумма, \(mask\) – маска присутствующих значении в массиве \(c\). \(dp_{n,0}=1\). Переберем \(c_0\) от \(0\) до \(M\), включительно. Пусть \(c_0=i\). Делаем переход в состояние \(dp_{(sum-i)/2,mask|2^i}\). Ответ будет лежать в \(dp_{0,fullmask}\), где \(fullmask\) – полная маска из первых \(M\) битов.

Можно понять, что количество посещаемых \(sum\) будет не более \(\log_2 n^2\). Так как \(dp\) не зависит от \(M\), то можно посчитать его один раз. Время работы: \(O(n \cdot \log_2 n^3)\).