#P17828. [Ontak2022]HSM
[Ontak2022]HSM
题目描述
递归定义超对称矩阵:
- 每个 矩阵都是超对称矩阵。
- 对于 ,一个 矩阵超对称,当且仅当它关于水平中轴、竖直中轴及两条主对角线均对称,并且令 后,四个角上的 子矩阵均超对称。
二进制矩阵的每个元素为0或1。将矩阵从第一行到最后一行、每行从左到右读出,得到一个 位二进制整数,称为矩阵的值;允许前导零。
把所有 超对称二进制矩阵的值从小到大排列,求第 小的值对 取模的结果。
输入格式
第一行一个十进制整数 。第二行给出 的二进制表示,首位为1。
输出格式
输出所求值模 的结果。
数据范围
;,且保证 不超过合法矩阵的数量。注意 本身最多可以有 个二进制位。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | n≤35 | 9 |
| 2 | n≤1500 | 18 |
| 3 | n≤100000 | 35 |
| 4 | n≤1000000 | 27 |
| 5 | 无额外限制 | 11 |
样例 1
输入:
4
1
输出:
0
样例 2
输入:
3
100
输出:
186
说明
第二个样例 k=(100)₂=4,对应矩阵为 010 / 111 / 010,按行读出的二进制数为186。