思路:独立计算每一位的贡献,考虑字符串$t$的每一位应该是什么字符,显然对于每一位应该填入的字符是字符串$s$循环左移得到的所有字符串中在该位出现次数最多的字符,此时产生的贡献是最大的
考虑如何计算在字符串$s$循环左移得到的所有字符串中,在每一位每个字符出现的次数,因为是循环左移$n$次,所以对于原字符串$s$中的每个字符会对$[1,n]$中的每一位各产生$1$的贡献,既然对于$s$中的每个字符在每一位产生的贡献是相同的,那么每一位的字符出现情况也是相同的,所以每一位的选法是相同的
代码实现:遍历$s$中的字符,统计$A、G、C、T$每个字符出现的次数,将次数从小到大排序,设从小到大排序后的出现次数分别为$cnt_0、cnt_1、cnt_2、cnt_3$,则有四种情况:
$1$、$cnt_3>cnt_2$,说明每一位都是选择出现次数最多的这个字符,则答案为$1$
$2$、$cnt_3=cnt_2且cnt_2>cnt_1$,说明每一位有$2$种选法,则答案为$2^n$
$3$、$cnt_3=cnt_2=cnt_1且cnt_1>cnt_0$,说明每一位有$3$种选法,则答案为$3^n$
$4$、$cnt_3=cnt_2=cnt_1=cnt_0$,说明每一位有$4$种选法,则答案为$4^n$
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int qmi(int a, int k)
{
int res = 1;
while (k)
{
if (k & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
k >>= 1;
}
return res;
}
void solve()
{
int n;
string s;
cin >> n >> s;
vector<int> cnt(4);
for (auto c : s)
if (c == 'A') cnt[0] ++ ;
else if (c == 'G') cnt[1] ++ ;
else if (c == 'C') cnt[2] ++ ;
else cnt[3] ++ ;
sort(cnt.begin(), cnt.end());
if (cnt[3] > cnt[2]) cout << 1 << "\n";
else if (cnt[2] > cnt[1]) cout << qmi(2, n) << "\n";
else if (cnt[1] > cnt[0]) cout << qmi(3, n) << "\n";
else cout << qmi(4, n) << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T -- ) solve();
return 0;
}
概括一下,就是最大的出现次数的出现次数(有点绕)的 $n$ 次方。