/* Exhaustive zero-forcing oracle for P(n,k), 2n <= 64 vertices.
 *
 * usage: brute_force n k s [m0]
 *   Enumerates every s-subset S of V(P(n,k)) (optionally only those whose
 *   lowest vertex id is m0, for parallel splitting), keeps only the subsets
 *   that are the minimum of their orbit under the dihedral group D_n acting
 *   by rotations and reflections (Proposition P3: orbit reduction loses no
 *   zero-forcing set), computes the closure by the colour-change rule, and
 *   reports how many representatives were tested and how many force the
 *   whole graph; the first forcing representative is printed as a witness.
 *
 * Vertex ids: u_i -> i, v_i -> n+i. Independent of the Python code: the
 * graph is rebuilt here from definition D1.
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

typedef uint64_t mask;

static int n, k, N;
static mask adj[64];
static int perm[128][64]; /* 2n group elements */
static int G;

static void build(void) {
    N = 2 * n;
    for (int i = 0; i < N; i++) adj[i] = 0;
    for (int i = 0; i < n; i++) {
        int u = i, u1 = (i + 1) % n, v = n + i, vk = n + (i + k) % n;
        adj[u] |= (mask)1 << u1; adj[u1] |= (mask)1 << u;
        adj[u] |= (mask)1 << v;  adj[v]  |= (mask)1 << u;
        adj[v] |= (mask)1 << vk; adj[vk] |= (mask)1 << v;
    }
    G = 0;
    for (int a = 0; a < n; a++) {
        for (int i = 0; i < n; i++) {
            perm[G][i] = (i + a) % n;           perm[G][n + i] = n + (i + a) % n;
            perm[G + 1][i] = ((a - i) % n + n) % n; perm[G + 1][n + i] = n + ((a - i) % n + n) % n;
        }
        G += 2;
    }
}

static inline mask closure(mask B) {
    mask full = (N == 64) ? ~(mask)0 : (((mask)1 << N) - 1);
    int changed = 1;
    while (changed) {
        changed = 0;
        mask rest = B;
        while (rest) {
            int b = __builtin_ctzll(rest);
            rest &= rest - 1;
            mask white = adj[b] & ~B;
            if (white && !(white & (white - 1))) { B |= white; changed = 1; }
        }
        if (B == full) return B;
    }
    return B;
}

static inline int canonical(mask m) {
    /* m is canonical iff no image under a nontrivial group element is smaller */
    for (int g = 1; g < G; g++) {
        mask img = 0, rest = m;
        while (rest) { int v = __builtin_ctzll(rest); rest &= rest - 1; img |= (mask)1 << perm[g][v]; }
        if (img < m) return 0;
    }
    return 1;
}

static void print_mask(mask m) {
    int first = 1;
    for (int w = 0; w < N; w++) if (m >> w & 1) {
        printf("%s%c%d", first ? "" : ",", w < n ? 'u' : 'v', w < n ? w : w - n);
        first = 0;
    }
}

int main(int argc, char **argv) {
    if (argc < 4) { fprintf(stderr, "usage: brute_force n k s [m0]\n"); return 2; }
    n = atoi(argv[1]); k = atoi(argv[2]); int s = atoi(argv[3]);
    int m0 = argc > 4 ? atoi(argv[4]) : -1;
    build();
    mask full = (N == 64) ? ~(mask)0 : (((mask)1 << N) - 1);
    unsigned long long enumerated = 0, tested = 0, forcing = 0;
    mask witness = 0;
    /* Gosper enumeration of t-subsets of the vertices > m0 (or all s-subsets) */
    int lo = (m0 >= 0) ? m0 + 1 : 0;
    int t = (m0 >= 0) ? s - 1 : s;
    int width = N - lo;
    if (t > width || t < 0) { printf("n=%d k=%d s=%d m0=%d enumerated=0 tested=0 forcing=0\n", n, k, s, m0); return 0; }
    mask base = (m0 >= 0) ? ((mask)1 << m0) : 0;
    mask sub = (t == 0) ? 0 : (((mask)1 << t) - 1);
    mask limit = (width == 64) ? ~(mask)0 : (((mask)1 << width) - 1);
    while (1) {
        mask m = base | (sub << lo);
        enumerated++;
        if (canonical(m)) {
            tested++;
            if (closure(m) == full) { if (!forcing) witness = m; forcing++; }
        }
        if (t == 0) break;
        /* next Gosper */
        mask c = sub & -sub, r = sub + c;
        if (r > limit || r == 0) break;
        sub = (((r ^ sub) >> 2) / c) | r;
        if (sub > limit) break;
    }
    printf("n=%d k=%d s=%d m0=%d enumerated=%llu tested=%llu forcing=%llu", n, k, s, m0, enumerated, tested, forcing);
    if (forcing) { printf(" witness="); print_mask(witness); }
    printf("\n");
    return 0;
}