Expert.
Put your skills to the test.

Problem summary

Letters A,B,C,D multiply by the Klein-four-group table: A is identity, every letter squares to A, and B⊗C=D. Given a k-letter target a and n, output n pairwise distinct k-letter words, all different from a, whose coordinatewise product is a.

Constraints

3 ≤ k ≤ 16; 3 < n ≤ 4^k/2. Output size can itself be very large.

Worked example

Official statement example.

ADC
8

AAC
ACA
CAA
CAB
BAD
BBD
CAC
CAD

Solution analysis

1. Encode A,B,C,D as 00,01,10,11. Multiplication is bitwise XOR of the resulting 2k-bit integers. Choose n−2 initial distinct integers, excluding target a, from the beginning of the integer range. Their membership is represented by an interval with at most one excluded target.
2. Let t be a XOR the XOR of the chosen prefix. The last two numbers must have XOR t. If t=0, replace the largest chosen number by a new number outside the prefix, making t nonzero. Membership still needs only an interval and at most two exceptions.
3. Find x such that both x and x XOR t are unused and different from a. There are n−1 forbidden numbers, and at most 2(n−1)<4^k forbidden x values; a suitable x therefore exists. In the official example the eight words XOR to ADC, and all eight are distinct and avoid ADC. The program may print another valid construction.

Why it works

The prefix has n−2 legal distinct values. If replaced, the added number is new and different from the removed one, so a formerly zero t becomes nonzero. For each forbidden value f, at most x=f and x=f XOR t are disallowed. Since their union has size below the universe, a valid x exists. The final pair is distinct because t≠0, avoids the prefix and target, and has XOR t, making the total XOR exactly a.

Watch out. Use a 64-bit unsigned type: 4^16 is 2^32.,The target itself is forbidden even when it equals zero.,Two equal final numbers are invalid.

Constructive output: any valid set is accepted; the program need not reproduce the example words.

// Key idea: The prefix has n−2 legal distinct values. If replaced, the added number is new and
// different from the removed one, so a formerly zero t becomes nonzero.
#include<cstdint>
#include<iostream>
#include<string>
using namespace std;
using U=uint64_t;
U prefixXor(U count){
    if(count==0){
        return 0;
    }
    U x=count-1;
    switch(x%4){
        case 0:
            return x;
        case 1:
            return 1;
        case 2:
            return x+1;
        default:
            return 0;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string word;
    U n;
    cin>>word>>n;
    U target=0;
    for(char c:word){
        target=(target<<2)|U(c-'A');
    }
    U count=n-2;
    U limit=count+(target<count?1:0);
    U total=prefixXor(limit);
    if(target<limit){
        total^=target;
    }
    U t=target^total;
    U removed=U(-1),added=U(-1);
    if(t==0){
        removed=limit-1;
        if(removed==target){
            --removed;
        }
        added=limit;
        if(added==target){
            ++added;
        }
        t^=removed^added;
    }
    auto forbidden=[&](U x){
        return x==target||x==added||(x<limit&&x!=removed);
    };
    U x=0;
    while(forbidden(x)||forbidden(x^t)){
        ++x;
    }
    auto emit=[&](U value){
        string out(word.size(),'A');
        for(int i=int(out.size())-1;i>=0;--i){
            out[i]=char('A'+(value&3));
            value>>=2;
        }
        cout<<out<<'\n';
    };
    for(U v=0;v<limit;++v){
        if(v!=target&&v!=removed){
            emit(v);
        }
    }
    if(added!=U(-1)){
        emit(added);
    }
    emit(x);
    emit(x^t);
}