#P6855. [2024年山东第二轮集训]交换比特
[2024年山东第二轮集训]交换比特
交换比特
题目描述
有 个带有不同编号的比特从左到右排成一排,初始编号依次为 至 ,相邻位置之间的距离为 。
你可以进行若干次操作(也可以不操作):选择 ,交换当前从左往右第 个和第 个比特。但是,每个位置下标 最多只能被选择一次。
一个比特的自由度定义为其最终位置与初始位置的距离,即位移的绝对值。
对于 、,令 表示所有可达到的、本质不同的最终局面中,恰好有 个比特的自由度等于 的局面数。两个局面不同,当且仅当至少一个位置上的比特编号不同;不同操作顺序若得到同一局面,只计一次。
给定 ,对每个 ,输出
输入格式
第一行两个整数 。
第二行 个整数 。
输出格式
输出 行,第 行表示自由度为 时的答案。
样例输入 1
3 998244353
1 2 3 4
样例输出 1
13
7
样例解释 1
所有 种全排列中,唯一无法得到的是 。有 个可达排列没有自由度为 的比特,有 个可达排列恰好有 个自由度为 的比特,因此第二行输出 。
样例输入 2
10 998244353
10 9 8 7 6 5 4 3 2 1 0
样例输出 2
18942
33958
39148
40922
41520
41718
41782
41802
41808
大样例
见原题下发文件。
数据范围
所有数据满足 ,, 为质数,。
| 测试点编号 | 的上界 | 其他限制 |
|---|---|---|
| 无 | ||
| 所有 | ||
| 无 |