OI XXX - wir (Fast)

// https://szkopul.edu.pl/problemset/problem/c9kbLOJVLHiQDcmiNo8Pa4w6/site/?key=statement

#include <bitset>
#include <iostream>
#include <vector>

// runs in 0.00s

#pragma GCC optimize("O3,unroll-loops")

constexpr int BUF_SZ = 1 << 18;
struct FastIO {
    char in_buf[BUF_SZ], out_buf[BUF_SZ];
    int in_ptr, in_len, out_ptr;

    FastIO() : in_ptr(0), in_len(0), out_ptr(0) {}

    inline char get_char() {
        if (in_ptr >= in_len) {
            in_ptr = 0;
            in_len = fread(in_buf, 1, BUF_SZ, stdin);
            if (in_len == 0) return 0;
        }
        return in_buf[in_ptr++];
    }

    template<typename T>
    inline void read(T& x) {
        x = 0;
        char c = get_char();
        while (c < '0' || c > '9')
            c = get_char();
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = get_char();
        }
    }

    template<size_t SIZE>
    inline void read_bits(int n, std::bitset<SIZE>& b) {
        for (int i = 0; i < n; ++i) {
            char c = get_char();
            while (c != '0' && c != '1')
                c = get_char();
            b[i] = (c == '1');
        }
    }

    inline void put_char(char c) {
        if (out_ptr >= BUF_SZ) flush();
        out_buf[out_ptr++] = c;
    }

    inline void flush() {
        fwrite(out_buf, 1, out_ptr, stdout);
        out_ptr = 0;
    }

    ~FastIO() { flush(); }
} io;

constexpr int MAXN = 705;
constexpr int MAX_DEG = 2 * MAXN;

using Poly = std::bitset<MAX_DEG>;

int n;

inline void reduce(Poly& p) {
    for (int i = 2 * n - 2; i >= n; --i) {
        if (p[i]) {
            p.flip(i - n + 1);
            p.flip(i - n);
            p[i] = 0;
        }
    }
}

Poly multiply(const Poly& A, const Poly& B) {
    Poly res;
    for (int i = 0; i < n; i++) {
        if (A[i]) {
            res ^= (B << i);
        }
    }
    reduce(res);
    return res;
}

Poly power(long long exp) {
    Poly res;
    res[0] = 1;

    Poly base;
    base[1] = 1;

    while (exp > 0) {
        if (exp & 1) {
            res = multiply(res, base);
        }

        Poly next_base;
        for (int i = 0; i < n; i++) {
            if (base[i]) {
                next_base[2 * i] = 1;
            }
        }
        reduce(next_base);
        base = next_base;

        exp >>= 1;
    }
    return res;
}

void solve() {
    long long d;
    io.read(n);
    io.read(d);

    std::bitset<MAXN> V;
    io.read_bits(n, V);

    if (d == 0) {
        for (int i = 0; i < n; i++)
            io.put_char(V[i] ? '1' : '0');
        io.put_char('\n');
        return;
    }

    Poly factors = power(d);

    std::bitset<MAXN> Ans;

    for (int k = 0; k < n; k++) {
        if (factors[k]) {
            Ans ^= V;
        }

        bool v0 = V[0];
        bool v1 = V[1];

        V >>= 1;
        V[n - 1] = (v0 != v1);
    }

    for (int i = 0; i < n; i++) {
        io.put_char(Ans[i] ? '1' : '0');
    }
    io.put_char('\n');
}

int32_t main() {
    solve();
    return 0;
}