Grox的序列七¶
- 参考时间限制：1.0 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB。
- 参考评测环境与测量
背景故事¶
我们的一些理论家认为Grox行为的动机，可能就是机械与有机生命体的差异性，然而没有任何方式能够检验这个假说。
——科学之书10（《Spore》，英文资料）
Grox 的思维令人着迷。经过长期的半机械化改造，他们的思考方式已经与其他生物大不相同，甚至包含矩阵的行列式。
你想起那个浪漫的文字矩阵：
\[
\det\begin{pmatrix}\text{我}&0&\text{生}\\0&\text{有}&0\\\text{你}&0&\text{幸}\end{pmatrix}=\text{我有幸}-\text{生有你}
\]
把减号看成汉字“一”，就成了“我有幸，一生有你”。不过，Grox 这次交来的既不是文字矩阵，也不是普通的数字矩阵，而是一个多项式矩阵；行列式的计算规则仍然相同。
Grox 想得到这个行列式的系数序列。由于项数和系数都可能很大，你需要按指定方式汇总系数，再将结果取模。
形式化问题描述¶
给定整数 \(k\) ，令 \(N=2^k\) .输入 \(N\) 个多项式，按 \(1\) 到 \(N\) 编号：
\[
A_i(x)=\sum_{j=0}^{N-1}a_{i,j}x^j
\]
构造 \(N\times N\) 多项式矩阵 \(M\) ，其中
\[
M_{r,i}=A_i(x)^{r-1}\qquad(1\le r,i\le N)
\]
第一行各元素均为常数多项式 \(1\) ，包括 \(A_i(x)=0\) 的情况。令
\[
B(x)=\det M=\sum_{t\ge0}b_t x^t
\]
对 \(0\le r<N\) ，计算
\[
V_r=\left(\sum_{\substack{t\ge0\\t\equiv r\pmod N}}b_t\right)\bmod P\qquad(P=1004535809)
\]
也就是把指数对 \(N\) 取余后，将同类项的系数相加。输出各系数的最小非负余数。
输入格式¶
第一行一个整数 \(k\) .接下来 \(N\) 行，第 \(i\) 行给出 \(N\) 个整数 \(a_{i,0},\ldots,a_{i,N-1}\) ，按次数从低到高排列。
输出格式¶
输出一行 \(N\) 个整数 \(V_0,\ldots,V_{N-1}\) ，以空格分隔。
样例¶
样例 1¶
输入¶
1
1 2
3 4
输出¶
2 2
样例 2¶
输入¶
0
999
输出¶
1
样例 3¶
输入¶
2
1 2 3 4
7 8 9 10
1 2 3 4
5 6 7 8
输出¶
0 0 0 0
样例解释¶
样例一的行列式为 \((3+4x)-(1+2x)=2+2x\) .样例二为一阶矩阵，行列式为 \(1\) .样例三有两列相同，行列式为零多项式。
数据范围与保证¶
对 100% 数据：
\(0\le k\le9\) ；\(0\le a_{i,j}\le999\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |