Codeforces 356B Xenia and Hamming：LCM 週期 + 同餘分組計數

問題重述

兩字符串 a、b，長度分別 la, lb。構造長度為 L = lcm(la,lb) 的超級串：a 重複 L/la 次，b 重複 L/lb 次。求兩超級串**漢明距離**（對應位置字符不同的個數）。最終答案乘以 n（a 的重複次數）。

核心觀察

在一個 LCM 週期內，a 的位置 i 僅與 b 的位置 j 配對，其中 i ≡ j (mod g)，g = gcd(la,lb)。
且每對 (i,j) **恰好配對一次**。

算法

1. 計算 g = gcd(la,lb)，L = la/g × lb。
2. 對餘數 r = 0..g−1，統計 a 中下標 ≡ r (mod g) 的字符頻率 `cntA[r][ch]`。
   同理統計 `cntB[r][ch]`。
3. 對每個 r，匹配字符數 = Σ_ch `cntA[r][ch]` × `cntB[r][ch]`。
   該餘數組總配對數 = (la/g) × (lb/g)？實際上每個 r 組內 a 有 la/g 個字符，b 有 lb/g 個，總配對 = (la/g) × (lb/g)？不，LCM 週期內每個 r 組貢獻 la/g × lb/g？
   正確：LCM 週期長度 L，每個 r 組恰好有 L/g 個位置？簡化：直接用代碼邏輯。
   代碼中 `sum = L`，然後減去匹配數。
4. 單週期漢明距離 = L − Σ_r,ch `cntA[r][ch]`·`cntB[r][ch]`。
   總答案 = (n × la / L) × 單週期距離 = n × la / L × ... = n / (lb/g) × ... 代碼中簡化為 `(n * la / L) * sum`。

代碼

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 n, m; string a, b;
    cin >> n >> m >> a >> b;
    int la = a.size(), lb = b.size();
    int g = std::gcd(la, lb);
    int64 L = 1LL * la / g * lb;
    vector> cntA(g), cntB(g);
    for (int i = 0; i < la; ++i) cntA[i % g][a[i]-'a']++;
    for (int i = 0; i < lb; ++i) cntB[i % g][b[i]-'a']++;
    int64 match = 0;
    for (int r = 0; r < g; ++r)
        for (int c = 0; c < 26; ++c)
            match += 1LL * cntA[r][c] * cntB[r][c];
    int64 periodHam = L - match;
    int64 ans = (n * la / L) * periodHam;
    cout << ans << '\n';
    return 0;
}

複雜度

O(la+lb+g×26)，線性極快。