串串异或

[题目链接](https://www.nowcoder.com/practice/6724661724314aa4ae0b1d4018ee9e34)

题意

定义两个字符串 （长度 ）和 （长度 ）的"异或"操作：

• 将两字符串右对齐，较短的字符串左侧用空格补齐；
• 从右往左逐位比较：相同则该位为 ，不同则该位为 ；
• 得到一个二进制串，将其转换为十进制输出（对 取模）。

思路

核心观察

对齐后，位置 （从末尾起， 索引）对应二进制数的第 位（即权重 ）。若该位字符不同，则答案加 。

因此：

$$

其中超出字符串范围的字符视为空格。

算法步骤

1. 从 到 遍历；
2. 取 末第 个字符（若 则为空格），取 末第 个字符（若 则为空格）；
3. 若两字符不同，将当前幂次 累加到答案；
4. 维护 ，每步乘以 即可（无需快速幂）。

时间复杂度： 每组数据。

样例验证

示例 2：abcdbab XOR agczzap（均长 7）

位	字符	字符	是否不同
0	b	p	是	1
1	a	a	否	-
2	b	z	是	4
3	d	z	是	8
4	c	c	否	-
5	b	g	是	32
6	a	a	否	-

答案 ，对应二进制 0101101，即 。

注意事项

• 模数为 （非常见的 ），需特别注意。
• 无需显式构造补齐后的字符串，直接用下标越界判断即可。

代码

C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const long long MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, m;
        cin >> n >> m;
        string a, b;
        cin >> a >> b;

        int maxLen = max(n, m);
        long long ans = 0;
        long long pw = 1;

        for (int i = 0; i < maxLen; i++) {
            char ca = (i < n) ? a[n - 1 - i] : ' ';
            char cb = (i < m) ? b[m - 1 - i] : ' ';

            if (ca != cb) {
                ans = (ans + pw) % MOD;
            }
            pw = pw * 2 % MOD;
        }

        cout << ans << "\n";
    }

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static final long MOD = 998244353L;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            String a = br.readLine().trim();
            String b = br.readLine().trim();

            int maxLen = Math.max(n, m);
            long ans = 0;
            long pw = 1;

            for (int i = 0; i < maxLen; i++) {
                char ca = (i < n) ? a.charAt(n - 1 - i) : ' ';
                char cb = (i < m) ? b.charAt(m - 1 - i) : ' ';

                if (ca != cb) {
                    ans = (ans + pw) % MOD;
                }
                pw = pw * 2 % MOD;
            }

            sb.append(ans).append('\n');
        }

        System.out.print(sb);
    }
}