Codeforces 520C DNA Alignment：貪心構造最大匹配序列

題目大意

給定長度 n（≤10⁵）的 DNA 序列 s（字符集 {A, C, G, T}）。定義 h(a, b) 為兩序列對應位置相同字符數。定義 p(s, t) 為對所有循環移位的 h 之和。求使 p 最大的序列 t 的個數，模 1e9+7。

關鍵觀察

p(s, t) = Σ_i Σ_j [s_i == t_j] = n × Σ_c (cnt_s[c] × cnt_t[c])。
因 n 固定，最大化 p 等價於最大化 Σ_c cnt_s[c] × cnt_t[c]。
對每個位置獨立選擇 t 的字符，貪心選擇 s 中出現次數最多的字符集合。設最大出現次數為 M，出現 M 次的字符種類數為 k，則每個位置有 k 種選擇，總方案數 = kⁿ。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

long long modpow(long long a, long long e) {
    long long r = 1;
    while (e) { if (e & 1) r = r * a % MOD; a = a * a % MOD; e >>= 1; }
    return r;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; string s; cin >> n >> s;
    int cnt[4] = {0}; // A, C, G, T
    for (char c : s) {
        if (c == 'A') ++cnt[0];
        else if (c == 'C') ++cnt[1];
        else if (c == 'G') ++cnt[2];
        else if (c == 'T') ++cnt[3];
    }
    int mx = *max_element(cnt, cnt+4);
    int k = 0; for (int x : cnt) if (x == mx) ++k;
    cout << modpow(k, n) << '\n';
    return 0;
}

複雜度

• 時間：O(n) 統計 + O(log n) 快速冪。
• 空間：O(1)。

範例

n=3, s="AGC"
cnt: A=1, C=1, G=1, T=0 → mx=1, k=3
答案 = 3^3 = 27

此題展示了如何將雙重求和轉化為頻率乘積，並利用貪心獨立決策每個位置的最優字符。