import std.algorithm;
import std.conv;
import std.format;
import std.range;
import std.stdio;

void main() {
    int[] z = [0,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1];

    z.heh.formatPolynom.writeln;
}

int[] heh(int[] z) {
    int r = 0;
    auto c = new int[z.length];
    auto b = new int[z.length];
    c[0] = b[0] = 1;

    while (r < z.length - 1) {
        r += 1;

        int d = 0;
        for (int j = 0; j < r; ++j) {
            d ^= c[j] * z[r-j-1];
        }

        auto xb = 0 ~ b[0..$-1];
        if (d == 0) {
            b = xb;
        }
        else {
            int[] t;
            foreach (k1, k2; zip(c, xb)) {
                t ~= k1 ^ k2;
            }
            b = c;
            c = t;
        }

        writefln("r=%s d=%s c=%s b=%s", r, d, c.formatPolynom, b.formatPolynom);
    }

    return c;
}

string formatPolynom(int[] p) {
    string[] strs;
    foreach (i, k; p) {
        if (i == 0 && k) strs ~= "1";
        if (i > 0 && k) strs ~= "x^" ~ i.to!string;
    }
    return strs.join(" + ");
}