#P9668. 手办

    ID: 6287 传统题 1000ms 512MiB 尝试: 61 已通过: 11 难度: 8 上传者: 标签>CF2500提高+/省选-一维前缀和单调队列滑动窗口最值周期规律验证快速幂

手办

题目描述

wygz 有 ∑ai\sum a_i 个 Dimoo。

为了拍出满意的照片,她把它们摆放在一个环上,第 ii 个位置上放 aia_i 个。位置按照顺时针的顺序从 11 到 nn 编号。

接下来的每一秒,wygz 会对所有同时进行操作:

  • 若 ii 上有至少一个 Dimoo,则拿起一个,放到下一个位置(也就是 (i+1) mod n(i+1) \bmod n)。

现在,wygz 想知道,经过 kk 秒以后,每个位置上会有多少个 Dimoo?

输入格式

第一行,两个整数,nn 和 kk。

第二行,nn 个非负整数,表示 aia_i。

输出格式

输出 ∑i=1nMi(ai+1) mod 264\sum_{i=1}^n M^i(a_i+1) \bmod 2^{64} 的结果,其中 M=12345678901M=12345678901,aia_i 为最终的答案序列。

样例

5 3
1 0 0 1 0
979919941747309627

最后的答案是 0 1 0 1 0。

5 3
0 1 2 0 0
16075001298286537116

最后的答案是 1 0 0 1 1。

6 4
0 1 5 5 0 5
15866784849838457306

最后的答案是 1 1 4 5 1 4。

数据范围

由于 [数据删除]的出题人偷偷加 0 输入量比较大,我们下发了 std 所使用的快速输入(即 io.cpp)供大家参考。时空限制均为 std 所耗的两倍以上。

对于全部数据,1≤n≤1071\le n\le 10^7,0≤k,ai≤1090\le k,a_i\le 10^9。

Subtask 特殊限制 分值
11 n,k≤1000n,k\le 1000 2020
22 n≤1000n\le 1000
33 ai∈{0,1}a_i\in \{0,1\} 11
44 n,k≤105n,k\le 10^5 1919
55 n≤105n\le 10^5 1010
66 n≤106n\le 10^6
77 无 2020