#P18375. Circular Convolution 2

Circular Convolution 2

Circular Convolution 2

题目描述

小青鱼凭借以 O(n1.999)O(n^{1.999}) 时间解决 (min⁡,+)(\min,+) 卷积问题的成果,获得了 5202 年 FOCS 最佳论文奖。现在,他想请你解决下面的问题。

对于两个长度为 nn 的序列 a=(a0,a1,…,an−1)a=(a_0,a_1,\ldots,a_{n-1})、b=(b0,b1,…,bn−1)b=(b_0,b_1,\ldots,b_{n-1}),定义它们的 (min⁡,+)(\min,+) 循环卷积 a×ba\times b 为长度为 nn 的序列,满足

$$(a\times b)_k=\min_{\substack{0\le i,j<n\\ i+j\equiv k\pmod n}}(a_i+b_j),\qquad 0\le k<n.$$

对正整数 tt,定义序列的 tt 次幂:a1=aa^1=a,当 t>1t>1 时,at=at−1×aa^t=a^{t-1}\times a。

给你一个随机生成的长度为 nn 的序列 aa,请计算 ana^n,也就是 nn 个 aa 进行上述循环卷积的结果。

输入格式

第一行一个整数 nn(1≤n≤5×1051\le n\le5\times10^5)。

第二行 nn 个整数 a0,a1,…,an−1a_0,a_1,\ldots,a_{n-1}(1≤ai≤1091\le a_i\le10^9)。

**随机输入保证:**每个元素均在整数区间 [1,109][1,10^9] 中独立、等概率地生成。全部测试数据(包括样例)总计不超过 100 组。

每个输入文件只有一个序列,首行不是测试用例数。

输出格式

输出一行 nn 个整数 c0,c1,…,cn−1c_0,c_1,\ldots,c_{n-1},表示 ana^n。

样例输入 1

2
82688973 409689707

样例输出 1

165377946 492378680

样例输入 2

3
965805101 983238551 643391778

样例输出 2

1930175334 2252588657 2270022107