AcWing 5154. 牛的基因学
原题链接
困难
作者:
无双飞怪
,
2024-04-19 17:07:00
,
所有人可见
,
阅读 3
//s: a b c d e->b c d e a ->c d e a b(这里两两之间的变化就叫做循环移位一次)
把s和t循环移位n次的结果两两配对 共有n^2对 看若两个对应位置相等则加一
t中每个字母对答案的贡献等于S中所有与t当前字母相同的字母的个数 要构造t使得结果最大 只需让t每个字母都取s中出现次数最多的字母即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,mod=1e9+7;
char str[N];
int hashs[100];
int main()
{
int n;
cin>>n;
scanf("%s",str);
int maxn=0;
int t=0;
for(int i=0;i<n;i++)
{
++hashs[str[i]];
if(hashs[str[i]]>maxn) maxn=hashs[str[i]],t=1;
else if(hashs[str[i]]==maxn) t++;
}
long long res=1;
for(int i=0;i<n;i++) res=(res*t)%mod;
cout<<res;
return 0;
}