题解 | #小红的字符串构造#

高斯消元的解法

每个位置我们要么选 $a$ ，要么选 $b$ ，我们不妨先全部选 $a$ ，然后考虑翻转一些位置（即选 $b$ ）。

用 $status_i, i=0 \sim 25$ 表示当前 26 个字母数量的奇偶性，当我们翻转 $l$ 号位置时，会同时翻转 $status_{a_l}$ 和 $status_{b_l}$ 。

注意到翻转 $(a_i,b_i)=(x,y)$ 和翻转 $(a_i,b_i)=(y,x)$ 的作用相同，所以一个翻转操作可以表示成 < $x,y$ > $(x<y)$ ，并且同一类型的操作进行两次相当于没有翻转。

于是我们可以统计 $cnt_{i,j}, 0 \le i < j \le 25$ 表示是否可以操作 < $i,j$ >。

我们设 $x_{i,j}$ 表示最终是否操作无序对 < $i,j$ >，于是可以列出如下方程：

$\begin{cases} cnt_{0,1} * x_{0,1} + cnt_{0,2} * x_{0,2} + \dots + cnt_{0,25} * x_{0,25} = status_0 \mod 2 \\ cnt_{0,1} * x_{0,1} + cnt_{1,2} * x_{1,2} + \dots + cnt_{1,25} * x_{1,25} = status_1 \mod 2 \\ \dots \\ cnt_{0,25} * x_{0,25} + cnt_{1,25} * x_{1,25} + \dots + cnt_{24,25} * x_{24,25} = status_{25} \mod 2 \end{cases}$

如果解方程得到所有 $x_{i,j}$ ，若 $x_{i,j}=1$ ，那就说明翻转过 < $i,j$ >，随意找个 $(a_l,b_l)=(i,j)$ 的位置选择 $b_l$ 即可。上述推理过程是充要的，如果方程无解，那么原问题也就无解。

我们只关注 $x_{i,j}$ 的奇偶性，可以使用 $bitset$ 优化高斯消元。

复杂度 $O(26^4/64)$

代码如下：

#include<iostream>
#include<bitset>
using namespace std;
using ll=long long;

constexpr int N = 26;
int ed[26], cnt[26][26], pos[26][26];

struct Gauss {// index-0
    bitset<N*N+1> A[N];// 第m列是常数列
    int x[N*N];
    void print(int n,int m) {
        cerr<<endl<<n<<"*"<<m<<" Matrix:"<<endl;
        for(int i=0; i<n; ++i) {
            for(int j=0; j<m; ++j)
                cerr<<A[i][j];
            cerr<<A[i][m]<<endl;
        }
    }
    bool solve(int n,int m) {
        int c=0, r=0;
        for(; r<n && c<m; ++r, ++c) {
            int r1=-1;
            for(int i=r; i<n; ++i)
                if(A[i][c]) {
                    r1=i;
                    break;
                }
            if(r1==-1) {
                --r;
                continue;
            }
            if(r1!=r)
                swap(A[r],A[r1]);
            for(int i=0; i<n; ++i) {
                if(i==r || !A[i][c]) continue;
                A[i]^=A[r];
            }
        }
        for(int i=r; i<n; ++i)
            if(A[i][m])
                return false;
        for(int i=0,j=0; j<m; ++i,++j) {
            while(j<m && (i>=n||!A[i][j]) )
                x[j++]=0;// free
            if(j<m)
                x[j]=A[i][m];
        }
        return true;
    }
} g;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    for(int i=0; i<n; ++i) {
        ed[a[i]-'a']^=1;
        int x=a[i]-'a';
        int y=b[i]-'a';
        if(x>y) swap(x,y);
        if(x<y) cnt[x][y]++, pos[x][y]=i;
    }

    int nn=0;
    for(int i=0; i<26; ++i) {
        for(int j=0; j<26; ++j) {
            if(cnt[i][j]) {
                g.A[i][nn]=1;
                g.A[j][nn]=1;
                nn++;
            }
        }
    }
    for(int i=0; i<26; ++i)
        if(ed[i])
            g.A[i][nn]=1;
    
    // g.print(26,nn);
    if(g.solve(26,nn)) {
        int nn=0;
        for(int i=0; i<26; ++i) {
            for(int j=0; j<26; ++j) {
                if(cnt[i][j]) {
                    if(g.x[nn])
                        swap(a[pos[i][j]], b[pos[i][j]]);
                    nn++;
                }
            }
        }
        cout<<a;
    }else {
        cout<<"-1\n";
    }
    return 0;
}
/*




*/