题解 | 小红的字符串构造

考虑二十六个字母拆成二十六位，先使用 a 串，同时将变化插入异或线性基，然后用线性基将权值消到 0

#include <array>
#include <iostream>
#include <valarray>
#include <vector>
using namespace std;

int n;
string a;
string b;

array<int, 26> xxj;
array<int, 26> xxjp;
array<int, 26> xxjMask;

void Insert(int x, int idx) {
    int mask = 0;
    for (int i = 25; i > -1; i--) {
        if (x & (1 << i)) {
            if (!xxj[i]) {
                xxj[i] = x;
                xxjp[i] = idx;
                xxjMask[i] = mask ^ (1 << i);
                return;
            }
            x ^= xxj[i];
            mask ^= xxjMask[i];
        }
    }
}

void Solve() {
    cin >> n >> a >> b;
    int cur = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i] - 'a';
        int y = b[i] - 'a';
        cur ^= 1 << x;
        Insert(1 << x ^ 1 << y, i);
    }
    int curMask = 0;
    for (int i = 25; i > -1; i--) {
        // cout << cur << ',' << xxj[i] << endl;
        if (cur & (1 << i)) {
            if (!xxj[i]) {
                cout << "-1";
                return;
            }
            curMask ^= xxjMask[i];
            cur ^= xxj[i];
        }
    }
    for (int i = 0; i < 26; i++) {
        if (curMask & (1 << i)) {
            a[xxjp[i]] = b[xxjp[i]];
        }
    }
    cout << a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
}
// 64 位输出请用 printf("%lld")