#P6855. [2024年山东第二轮集训]交换比特

    ID: 6686 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-组合数学双射计数字符串游程编码多项式与生成函数有理生成函数生成函数求系数动态规划计数 DP线性代数与代数线性递推CF2900

[2024年山东第二轮集训]交换比特

交换比特

题目描述

有 NN 个带有不同编号的比特从左到右排成一排,初始编号依次为 11 至 NN,相邻位置之间的距离为 11。

你可以进行若干次操作(也可以不操作):选择 1≤i≤N−11\le i\le N-1,交换当前从左往右第 ii 个和第 i+1i+1 个比特。但是,每个位置下标 ii 最多只能被选择一次。

一个比特的自由度定义为其最终位置与初始位置的距离,即位移的绝对值。

对于 1≤i≤N−11\le i\le N-1、0≤j≤N0\le j\le N,令 fi,jf_{i,j} 表示所有可达到的、本质不同的最终局面中,恰好有 jj 个比特的自由度等于 ii 的局面数。两个局面不同,当且仅当至少一个位置上的比特编号不同;不同操作顺序若得到同一局面,只计一次。

给定 a0,a1,…,aNa_0,a_1,\ldots,a_N,对每个 i=1,…,N−1i=1,\ldots,N-1,输出

∑j=0Najfi,j(modM).\sum_{j=0}^{N}a_jf_{i,j}\pmod M.

输入格式

第一行两个整数 N,MN,M。

第二行 N+1N+1 个整数 a0,a1,…,aNa_0,a_1,\ldots,a_N。

输出格式

输出 N−1N-1 行,第 ii 行表示自由度为 ii 时的答案。

样例输入 1

3 998244353
1 2 3 4

样例输出 1

13
7

样例解释 1

所有 66 种全排列中,唯一无法得到的是 (3,2,1)(3,2,1)。有 33 个可达排列没有自由度为 22 的比特,有 22 个可达排列恰好有 11 个自由度为 22 的比特,因此第二行输出 1×3+2×2=71\times3+2\times2=7。

样例输入 2

10 998244353
10 9 8 7 6 5 4 3 2 1 0

样例输出 2

18942
33958
39148
40922
41520
41718
41782
41802
41808

大样例

见原题下发文件。

数据范围

所有数据满足 1≤N≤20001\le N\le2000,0.99×109≤M≤1.01×1090.99\times10^9\le M\le1.01\times10^9,MM 为质数,0≤ai<M0\le a_i<M。

测试点编号 NN 的上界 其他限制
11 1010 无
22 1818
3,43,4 100100
5,65,6 500500
77 20002000 所有 ai=1a_i=1
8,9,108,9,10 无