Codeforces Round 754 (Div. 2) |
---|
Закончено |
Целочисленный массив $$$a$$$ длины $$$n$$$ называется палиндORмом, если ($$$a_{1}$$$ $$$|$$$ $$$a_{2} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ a_{i}) = (a_{{n - i + 1}} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ a_{{n - 1}} $$$ $$$|$$$ $$$ a_{n}) $$$ для всех $$$ 1 \leq i \leq n$$$, где $$$|$$$ обозначает операцию побитового ИЛИ.
Целочисленный массив $$$a$$$ длины $$$n$$$ считается хорошим, если его элементы могут быть переставлены так, чтобы образовать палиндORм. Формально, массив $$$a$$$ является хорошим, если существует перестановка $$$p_1, p_2, \ldots p_n$$$ (массив, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз), для которой $$$a_{p_1}, a_{p_2}, \ldots a_{p_n}$$$ является палиндORмом.
Найдите количество хороших массивов длины $$$n$$$, состоящих только из целых чисел в диапазоне $$$[0, 2^{k} - 1]$$$, и выведите его по модулю некоторого простого числа $$$m$$$.
Два массива $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$ считаются различными, если существует индекс $$$i$$$ $$$(1 \leq i \leq n)$$$ такой, что $$$a_i \ne b_i$$$.
Первая и единственная строка входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$m$$$ ($$$1 \leq n,k \leq 80$$$, $$$10^8 \lt m \lt 10^9$$$). Гарантируется, что $$$m$$$ является простым.
Выведите одно целое число — количество хороших массивов по модулю $$$m$$$.
1 1 998244353
2
3 2 999999733
40
7 3 796735397
1871528
2 46 606559127
177013
В первом примере оба возможных массива $$$[0]$$$ и $$$[1]$$$ являются хорошими.
Во втором примере есть несколько примеров хороших массивов:
Обратите внимание, что $$$[1, 1, 0]$$$, $$$[1, 0, 1]$$$ и $$$[0, 1, 1]$$$ являются хорошими массивами и считаются разными в соответствии с определением в утверждении.
В третьем примере примером хорошего массива является $$$[1, 0, 1, 4, 2, 5, 4]$$$. Его можно переставить в массив $$$b = [1, 5, 0, 2, 4, 4, 1]$$$, который является палиндORмом, потому что:
Здесь $$$\mathrm{OR}(l, r)$$$ обозначает $$$b_{l}$$$ $$$|$$$ $$$b_{l+1} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ b_{r}$$$
Название |
---|