程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 521A DNA Alignment 規律

Codeforces 521A DNA Alignment 規律

編輯：C++入門知識

Codeforces 521A DNA Alignment 規律

題意：

給定長度為n的一個字符串s。

構造長度也為n的字符串t。使得p(s,t)值最大，問有多少個不同的t

h(s,t) = 對應位置上字母相同的個數

ρ(AGC, CGT) = h(AGC, CGT) + h(AGC, GTC) + h(AGC, TCG) + h(GCA, CGT) + h(GCA, GTC) + h(GCA, TCG) + h(CAG, CGT) + h(CAG, GTC) + h(CAG, TCG) = 1 + 1 + 0 + 0 + 1 + 1 + 1 + 0 + 1 = 6 思路：

首先我們構造t的一個字母，那麼這個字母和s的任意一個字母在任意兩個位置都會匹配一次，而對應的次數有n次。所以構造的這個字母對答案貢獻是 Num[this_Letter] * n

如果t中填一個A，那麼p(s,t)的值就增加 (s中A字母個數)*n

所以為了使p最大，則t中能填的字母一定是s中字母數量最多那種。

則s中字母數量最多有多少種，t中每個位置上能填的字母就有多少種。

#include 
#include 
#include 

using namespace std;

const int MAX_N = 100007;
const long long mod = 1000000007;

long long Pow(long long x, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

char str[MAX_N];
int a[5], n;

int main() {
    scanf(%d%s, &n, str);
    for (int i = 0; str[i]; ++i) {
        if (str[i] == 'A') ++a[0];
        else if (str[i] == 'C') ++a[1];
        else if (str[i] == 'G') ++a[2];
        else ++a[3];
    }
    int up = 0;
    for (int i = 0; i < 4; ++i) up = max(up, a[i]);
    int cnt = 0;
    for (int i = 0; i < 4; ++i) if (a[i] == up) ++cnt;
    long long ans = Pow(cnt, n);
    printf(%I64d
, ans);
    return 0;
}