Description

Orez 很喜欢玩游戏, 他最近发明了一款硬币游戏. 他在桌子的边缘上划分出 \(2n\) 个位置并 按顺时针把它们标号为 \(1, 2, ..., 2n\), 然后把 \(n\) 个硬币放在标号为奇数的位置上. 接下来每次按如下操作: 在任意两个硬币之间放上一个硬币, 然后将原来的硬币拿走; 所放 硬币的正反面由它两边的两个硬币决定, 若两个硬币均为正面朝上或反面朝上, 则所放硬币为正面朝上, 否则为反面朝上. 那么操作 \(T\) 次之后桌子边缘上硬币的情况会是怎样的呢?

Input

文件的第一行包含两个整数 \(n\) 和 \(T\). 接下的一行包含 \(n\) 个整数, 表示最开始桌面边缘的硬币摆放情况, 第 \(i\) 个整数 \(a_i\) 表示第 \(i\) 个硬币摆放在 \(2i - 1\) 个位置上,\(a_i = 1\) 表示正面朝上,\(a_i = 2\) 表示反面朝上.

Output

文件仅包含一行, 为 \(2n\) 个整数, 其中第 \(i\) 个整数 \(b_i\) 桌面边缘的第 \(i\) 个位置上硬币的情况,\(b_i = 1\) 表示正面朝上,\(b_i = 2\) 表示反面朝上,\(b_i = 0\) 表示 没有硬币.

Sample Input

10 5
2 2 2 1 1 1 1 1 1 2

Sample Output

0 1 0 1 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 1

Data Range

对于 30% 的数据,\(n \leq 1000, T \leq 1000\)

对于 100% 的数据,\(n \leq 10^5, T \leq 2^{60}\)

Explanation

其实本题是这样的一道题 (题目中可能没有说清楚, 让我第一感觉和第二感觉...... 第 n 感觉 都认为这道题一定出错了): 每一次操作对于所有的硬币都在中间放一个. 不然完全随机 的事件怎么可能是可解的呢?

还有这是一圈硬币 (直接看数据并不能看出来, 看了好久也没有搞懂 233)

然后当然就应该去找规律了呵呵 (如果你强行暴力时间复杂度是 \(O(n T)\) 的)

突然发现我这里的值会在 \(2^k\) 个单位时间之后被距离 \(k\) 的点亦或到, 然后直接处理 一下 \(T\) 就可以在 \(O(n \log T)\) 时间复杂度内处理出这个结果了.

最后特判一下奇偶性, 如果是奇数再进行一轮 (记得考虑是一圈硬币)

顺便说一下三次提交记录: 第一次发现是个 PE, 然后最后一行需要以换行结尾而且最尾部 不能有多余的空格; 第二次交上去 TLE 实在搞不懂, 突然发现处理 \(T\) 的时候用的是 32 位整形而不是 64 位整数就尴尬了; 第三次 AC 妥妥的~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxm = 200100;

lli n, m, work_pos;
int dp_arr[2][maxm], res[maxm];
#define dp_cur dp_arr[work_pos & 1]
#define dp_last dp_arr[!(work_pos & 1)]

int main(int argc, char** argv)
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        dp_arr[0][i] = x - 1;
    }
    // Finished reading data.
    // According to the general properties we found in this problem, we split
    // the digits of m in the following way, in binary.
    for (lli j = 2; j <= m; j <<= 1) if (m & j) {
        work_pos++;
        for (int i = 1; i <= n; i++) {
            int left = (i + (j>>1) % n + n - 1) % n + 1,
                right = (i - (j>>1) % n + n - 1) % n + 1;
            dp_cur[i] = dp_last[left] ^ dp_last[right];
        }
    }
    rep(i, 1, n) res[i + i - 1] = dp_cur[i];
    // Checking speacial occasions, onwhich data must be shifted.
    if (m & 1) { // Odd cases
        rep(i, 1, n) res[i + i] = res[i + i - 1] ^ res[i >= n ? 1 : i + i + 1];
        rep(i, 1, n) res[i + i - 1] = -1;
    } else {
        rep(i, 1, n) res[i + i] = -1;
    }
    // A peculiar and obscured output...
    for (int i = 1; i < 2 * n; i++)
        printf("%d ", res[i] + 1);
    printf("%d\n", res[2 * n] + 1);
    return 0;
}