?
题意：
给定长度为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; }
?