PalindORme
Contest: Codeforces Round 754 (Div. 2)
Difficulty rating: 2900
Tags: combinatorics, dp

An integer array $$$a$$$ of length $$$n$$$ is said to be a PalindORme if ($$$a_{1}$$$ $$$|$$$ $$$a_{2} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ a_{i}) = (a_{{n - i + 1}} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ a_{{n - 1}} $$$ $$$|$$$ $$$ a_{n}) $$$ for all $$$ 1 \leq i \leq n$$$, where $$$|$$$ denotes the bitwise OR operation.

An integer array $$$a$$$ of length $$$n$$$ is considered to be good if its elements can be rearranged to form a PalindORme. Formally, array $$$a$$$ is good if there exists a permutation $$$p_1, p_2, \ldots p_n$$$ (an array where each integer from $$$1$$$ to $$$n$$$ appears exactly once) for which $$$a_{p_1}, a_{p_2}, \ldots a_{p_n}$$$ is a PalindORme.

Find the number of good arrays of length $$$n$$$, consisting only of integers in the range $$$[0, 2^{k} - 1]$$$, and print it modulo some prime $$$m$$$.

Two arrays $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$ are considered to be different if there exists any $$$i$$$ $$$(1 \leq i \leq n)$$$ such that $$$a_i \ne b_i$$$.

Input format:
The first and only line of the input contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \leq n,k \leq 80$$$, $$$10^8 \lt m \lt 10^9$$$). It is guaranteed that $$$m$$$ is prime.

Output format:
Print a single integer  — the number of good arrays modulo $$$m$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first sample, both the possible arrays $$$[0]$$$ and $$$[1]$$$ are good.

In the second sample, some examples of good arrays are:

- $$$[2, 1, 2]$$$ because it is already PalindORme.
- $$$[1, 1, 0]$$$ because it can rearranged to $$$[1, 0, 1]$$$ which is PalindORme

Note that $$$[1, 1, 0]$$$, $$$[1, 0, 1]$$$ and $$$[0, 1, 1]$$$ are all good arrays and are considered to be different according to the definition in the statement.

In the third sample, an example of a good array is $$$[1, 0, 1, 4, 2, 5, 4]$$$. It can be rearranged to an array $$$b = [1, 5, 0, 2, 4, 4, 1]$$$ which is a PalindORme because:

- $$$\mathrm{OR}(1, 1)$$$ = $$$\mathrm{OR}(7, 7)$$$ = $$$1$$$
- $$$\mathrm{OR}(1, 2)$$$ = $$$\mathrm{OR}(6, 7)$$$ = $$$5$$$
- $$$\mathrm{OR}(1, 3)$$$ = $$$\mathrm{OR}(5, 7)$$$ = $$$5$$$
- $$$\mathrm{OR}(1, 4)$$$ = $$$\mathrm{OR}(4, 7)$$$ = $$$7$$$
- $$$\mathrm{OR}(1, 5)$$$ = $$$\mathrm{OR}(3, 7)$$$ = $$$7$$$
- $$$\mathrm{OR}(1, 6)$$$ = $$$\mathrm{OR}(2, 7)$$$ = $$$7$$$
- $$$\mathrm{OR}(1, 7)$$$ = $$$\mathrm{OR}(1, 7)$$$ = $$$7$$$

Here $$$\mathrm{OR}(l, r)$$$ denotes $$$b_{l}$$$ $$$|$$$ $$$b_{l+1} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ b_{r}$$$

Example input:
1 1 998244353

Example output:
2

Example input:
3 2 999999733

Example output:
40

Editorial:
$$$\textbf{Solution Outline:}$$$
For any bad array, there is $$$\textbf{exactly one}$$$ maximum even length good subsequence (possibly the empty subsequence).
It can be proven that there exists at most one element in the bad array that doesn't belong to this subsequence, but is a submask of its OR. If such an element exists, we add it to the subsequence. After performing this step if needed, we have a good subsequence of this bad array such that all other elements of this array have one or more bits active which aren't present anywhere in this subsequence. We will call this the "best" subsequence from now on. Clearly a bad array also has $$$\textbf{exactly one}$$$ best subsequence.
By noting that the best subsequence is still a good array (place the extra element in the middle of the PalindORme of even length), we can use dp to count the number of bad arrays of length $$$n$$$ with exactly $$$k$$$ bits on in total using its best subsequence of length $$$n' \lt n$$$ with exactly $$$k' \lt k$$$ bits on in total in $$$O(n ^ 4)$$$.
$$$\textbf{Full Editorial:}$$$
Let $$$S$$$ be the multiset of elements of the initial array $$$a_1, a_2, \ldots, a_n$$$. We want to check if we can construct a PalindORme from these elements.
Out of the $$$n$$$ conditions of the form $$$b_{1}$$$ $$$|$$$ $$$b_{2} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ b_{i} = b_{{n - i + 1}} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ b_{{n - 1}} $$$ $$$|$$$ $$$ b_{n} $$$, it intuitively makes sense to tackle them in increasing order of $$$i$$$, so we will try to do that.
• For $$$i = 1$$$, we want to find two elements $$$x, y$$$ in $$$S$$$ such that $$$x = y$$$. We place these elements as $$$b_1$$$ and $$$b_n$$$ and erase them from $$$S$$$.
• For $$$i = 2$$$, we want to find two elements $$$x, y$$$ in $$$S$$$ such that $$$b_1$$$ $$$|$$$ $$$x$$$ $$$=$$$ $$$b_1$$$ $$$|$$$ $$$y$$$. We place these elements as $$$b_2$$$ and $$$b_{n - 1}$$$ and erase them from $$$S$$$.
• Generalizing, for any $$$i$$$, we want to find two elements $$$x, y$$$ in $$$S$$$ such that $$$b_{1}$$$ $$$|$$$ $$$b_{2} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ b_{i - 1}$$$ $$$|$$$ $$$x$$$ $$$=$$$ $$$b_{1}$$$ $$$|$$$ $$$b_{2} $$$ $$$|$$$ $$$ \ldots $$$ $$$|$$$ $$$ b_{i - 1}$$$ $$$|$$$ $$$y$$$. We place these elements as $$$b_i$$$ and $$$b_{n + 1 - i}$$$ and erase them from $$$S$$$.
But what if there exists multiple pairs $$$(x_1, y_1), (x_2, y_2), \ldots (x_k, y_k)$$$ that satisfy the property in a given step, which do we take?
It is optimal to take any of them. Clearly if $$$mask$$$ $$$|$$$ $$$x_j$$$ = $$$mask$$$ $$$|$$$ $$$y_j$$$, then $$$mask$$$ $$$|$$$ $$$z$$$ $$$|$$$ $$$x_j$$$ = $$$mask$$$ $$$|$$$ $$$z$$$ $$$|$$$ $$$y_j$$$ is also true for any $$$z$$$. So regardless of which of these pairs we take, all other pairs will remain good in future steps.
So we obtain the following simple algorithm to check if a PalindORme is good:
This algorithm is equivalent to placing elements at positions $$$i$$$ and $$$(n + 1 - i)$$$ of the PalindORme in the $$$i$$$-th iteration of the loop. Taking any two elements is optimal since a pair that satisfies the property for $$$mask$$$ will also clearly satisfy it for $$$mask$$$ $$$|$$$ $$$x$$$.
Let us consider the multiset $$$S$$$ corresponding to the elements of a bad array:
• This algorithm will fail to find any such pair of elements after some number of steps.
• The pairs which have been selected till this point will constitute a good array (possibly of length 0).
• For the given bad array, the number of pairs taken as well as the bits on in the mask will always be the same when the algorithm fails regardless of the two elements selected in each step.
• Since we cannot add any two more elements to this good array, this is the longest even length good subsequence of the bad array. Due to the previous point, we can also see that it is the only good subsequence of this length.
• There can exist at most one element among the remaining elements not in the subsequence which is a submask of $$$mask$$$, otherwise there would exist a pair such that $$$mask$$$ $$$|$$$ $$$x$$$ $$$=$$$ $$$mask$$$ $$$|$$$ $$$y$$$ $$$=$$$ $$$mask$$$.
• If such an element exists, we can add it to the subsequence. The best subsequence still remains a good array since we can place this element in the center position of resulting PalindORme.
• After performing this step if needed, we have a good subsequence of this bad array such that all elements of this array not in the subsequence have one or more bits active which aren't on in $$$mask$$$ and therefore not present in the subsequence. We will call this the "best" subsequence from now on. Clearly a bad array also has $$$\textbf{exactly one}$$$ best subsequence (possibly of length 0).
So every bad array of length $$$n$$$ with $$$k$$$ bits on in total can be mapped to a best subsequence (which is a good array) with length $$$n' \lt n$$$ with $$$k' \lt k$$$ bits on in total. The remaining $$$n - n'$$$ elements will then need to be chosen such that they have the remaining $$$k - k'$$$ bits on in total while possessing distinct values when OR'd with $$$mask$$$.
So we obtain a dp to count the number of bad arrays $$$-$$$ $$$cnt\_bad_{\text{length}, \text{bits on in total}}$$$, where $$$cnt\_bad_{i, j} = \sum\limits_{i' = 0}^{i - 1} \sum\limits_{j' = 0}^{j - 1} f(i, j, i', j')\cdot(cnt\_good_{i', j'})$$$.
Here $$$f(i, j, i', j')$$$ is the number of bad arrays of length $$$i$$$ with exactly $$$j$$$ bits on in total, that have a good array of length $$$i' \lt i$$$ with exactly $$$j' \lt j$$$ bits on in total as their best subsequence.
Since the total number of arrays of length $$$x$$$ with exactly $$$y$$$ bits on in total can be easily calculated using some basic combinatorial formulas and inclusion exclusion, we can rewrite this as:
$$$cnt\_bad_{i, j}$$$ $$$=$$$ $$$\sum\limits_{i' = 0}^{i - 1} \sum\limits_{j' = 0}^{j - 1} f(i, j, i', j')\cdot(cnt\_total_{i', j'} - cnt\_bad_{i', j'})$$$
giving us a dp with $$$O(n ^ 2)$$$ states and $$$O(n ^ 4)$$$ transitions.
$$$f(i, j, i', j')$$$ is made of the following components:
1. The number of ways of placing the best subsequence in the bad array.    Since there are no values in common between the best subsequence and the remaining values of the array, the answer is just $$$n \choose n'$$$.
2. Since there are no values in common between the best subsequence and the remaining values of the array, the answer is just $$$n \choose n'$$$.
3. The number of ways of choosing which $$$j'$$$ of the $$$j$$$ bits were from the good array.    All ways are possible, so it is just $$$j \choose j'$$$
4. All ways are possible, so it is just $$$j \choose j'$$$
5. The number of different arrays of length $$$i - i'$$$ with the remaining $$$j - j'$$$ bits set in total such that each element has one or more of the $$$j - j'$$$ bits set and all elements have distinct values when OR'd with $$$mask$$$, i.e, the remaining $$$j$$$ bits.    We can observe that the second can be broken into the product of two easier parts:   The number of different arrays of $$$i - i'$$$ distinct positive numbers with exactly $$$j - j'$$$ bits set in total. We can first find the number of ways of permuting $$$i - i'$$$ positive numbers with $$$\textbf{up to}$$$ $$$k$$$ bits set in total as $$$^{2^k - 1} P_{i - i'}$$$. Then we just need to perform simple inclusion-exclusion to get the answer for exactly $$$k$$$ bits set in total.  The number of ways of setting the remaining $$$j'$$$ bits for these numbers. Since $$$mask$$$ is effectively the OR of all elements in the good array, all the $$$j'$$$ bits are already set in $$$mask$$$. So any setting of these $$$j'$$$ bits for these numbers doesn't doesn't affect the values when OR'd with $$$mask$$$. So the number of ways is just $$$2^{(i - i')\cdot(j')}$$$.
6. We can observe that the second can be broken into the product of two easier parts:   The number of different arrays of $$$i - i'$$$ distinct positive numbers with exactly $$$j - j'$$$ bits set in total. We can first find the number of ways of permuting $$$i - i'$$$ positive numbers with $$$\textbf{up to}$$$ $$$k$$$ bits set in total as $$$^{2^k - 1} P_{i - i'}$$$. Then we just need to perform simple inclusion-exclusion to get the answer for exactly $$$k$$$ bits set in total.  The number of ways of setting the remaining $$$j'$$$ bits for these numbers. Since $$$mask$$$ is effectively the OR of all elements in the good array, all the $$$j'$$$ bits are already set in $$$mask$$$. So any setting of these $$$j'$$$ bits for these numbers doesn't doesn't affect the values when OR'd with $$$mask$$$. So the number of ways is just $$$2^{(i - i')\cdot(j')}$$$.
7. The number of different arrays of $$$i - i'$$$ distinct positive numbers with exactly $$$j - j'$$$ bits set in total. We can first find the number of ways of permuting $$$i - i'$$$ positive numbers with $$$\textbf{up to}$$$ $$$k$$$ bits set in total as $$$^{2^k - 1} P_{i - i'}$$$. Then we just need to perform simple inclusion-exclusion to get the answer for exactly $$$k$$$ bits set in total.
8. The number of ways of setting the remaining $$$j'$$$ bits for these numbers. Since $$$mask$$$ is effectively the OR of all elements in the good array, all the $$$j'$$$ bits are already set in $$$mask$$$. So any setting of these $$$j'$$$ bits for these numbers doesn't doesn't affect the values when OR'd with $$$mask$$$. So the number of ways is just $$$2^{(i - i')\cdot(j')}$$$.
Since these three components are independent of each other, $$$f(i, j, i', j')$$$ is just the product of them.
However, as you may have observed, the "bad" arrays counted by this dp doesn't line up with the actual definition of bad arrays in one case - When a "bad" array has an even length best subsequence and a single remaining element with one or more bits that aren't set in this subsequence. This is clearly a good array but is counted as bad by our dp. (Example: good array [1, 1] combined with remaining element array [2] resulting in [1, 2, 1] (or [1, 1, 2] / [2, 1, 1]) which is clearly a good array but is counted as bad by our dp.)
This is however necessary since this is the only type of good array that is never the best subsequence of any bad array. Counting it as a good array in our dp would lead to overcounting when it was used as a best subsequence.
But then how do we then recover the correct number of actual bad arrays of length $$$n$$$ with exactly $$$j$$$ bits set? We can notice that this case occurs for best subsequences of length $$$i - 1$$$ when $$$i$$$ is odd. So when counting the number of bad arrays of length $$$n$$$ we can just skip best subsequences of length $$$n - 1$$$ if $$$n$$$ is odd. Since $$$n$$$ is the largest array size we are concerned with, good arrays of size $$$n$$$ will never be a best subsequence of a larger bad array and as such won't lead to overcounting.
As a final note, remember that we have the number of bad arrays for $$$n$$$ with $$$\textbf{exactly}$$$ $$$j$$$ bits set while we need the number of bad arrays with $$$\textbf {up to}$$$ $$$j$$$ bits set. This can be easily obtained by multiplying the answer for a given $$$j$$$ with the number of ways of choosing $$$j$$$ of the $$$k$$$ bits and summing these values up for each $$$j$$$. In short, we want $$$\sum_{j = 0}^{k} {k \choose j} \cdot cnt\_good_{n, j}$$$.
Time Complexity: $$$\mathcal{O}(n ^ 4)$$$
$$$$$$ \cdots $$$$$$