308967: CF1605F. PalindORme
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
PalindORme
题意翻译
称一个长度为 $n$ 的序列 $a$ 是 $\text{PalindORme}$ 的,当且仅当对于任意 $1 \le i \le n$,满足 $a_1 | a_2 | \dots | a_i = a_n | a_{n-1} | \dots |a_{n-i+1}$,其中 `|` 表示按位或运算。 称一个长度为 $n$ 的序列 $b$ 是 $\text{good}$ 的,当且仅当它可以重排成一个 $\text{PalindORme}$ 的序列。 给你 $n,k,m$,求长度为 $n$,每个元素值域为 $[0,2^k)$ 的序列中有多少个是 $\text{good}$ 的,对 $m$ 取模。题目描述
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](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 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 $ .输入输出格式
输入格式
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.
输出格式
Print a single integer — the number of good arrays modulo $ m $ .
输入输出样例
输入样例 #1
1 1 998244353
输出样例 #1
2
输入样例 #2
3 2 999999733
输出样例 #2
40
输入样例 #3
7 3 796735397
输出样例 #3
1871528
输入样例 #4
2 46 606559127
输出样例 #4
177013