#P18375. Circular Convolution 2
Circular Convolution 2
Circular Convolution 2
题目描述
小青鱼凭借以 时间解决 卷积问题的成果,获得了 5202 年 FOCS 最佳论文奖。现在,他想请你解决下面的问题。
对于两个长度为 的序列 、,定义它们的 循环卷积 为长度为 的序列,满足
$$(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.$$对正整数 ,定义序列的 次幂:,当 时,。
给你一个随机生成的长度为 的序列 ,请计算 ,也就是 个 进行上述循环卷积的结果。
输入格式
第一行一个整数 ()。
第二行 个整数 ()。
**随机输入保证:**每个元素均在整数区间 中独立、等概率地生成。全部测试数据(包括样例)总计不超过 100 组。
每个输入文件只有一个序列,首行不是测试用例数。
输出格式
输出一行 个整数 ,表示 。
样例输入 1
2
82688973 409689707
样例输出 1
165377946 492378680
样例输入 2
3
965805101 983238551 643391778
样例输出 2
1930175334 2252588657 2270022107