Codeforces520C-DNA Alignment
3342 단어 #쾌속멱Codeforces
Vasya became interested in bioinformatics. He's going to write an article about similar cyclic DNA sequences, so he invented a new method for determining the similarity of cyclic sequences.
Let's assume that strings s and t have the same length n, then the function h(s, t) is defined as the number of positions in which the respective symbols of s and t are the same. Function h(s, t) can be used to define the function of Vasya distance ρ(s, t):
where is obtained from string
s, by applying left circular shift
i times. For example,
ρ("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
Vasya found a string s of length n on the Internet. Now he wants to count how many strings t there are such that the Vasya distance from the string s attains maximum possible value. Formally speaking, t must satisfy the equation: .
Vasya could not try all possible strings to find an answer, so he needs your help. As the answer may be very large, count the number of such strings modulo 109 + 7.Input
The first line of the input contains a single integer n (1 ≤ n ≤ 105).
The second line of the input contains a single string of length n, consisting of characters "ACGT".
Output
Print a single number — the answer modulo 109 + 7.
Example
Input
1
C
Output
1
Input
2
AG
Output
4
Input
3
TTT
Output
1
Note
Please note that if for two distinct strings t1 and t2 values ρ(s, t1) и ρ(s, t2) are maximum among all possible t, then both strings must be taken into account in the answer even if one of them can be obtained by a circular shift of another one.
In the first sample, there is ρ("C", "C") = 1, for the remaining strings t of length 1 the value of ρ(s, t) is 0.
In the second sample, ρ("AG", "AG") = ρ("AG", "GA") = ρ("AG", "AA") = ρ("AG", "GG") = 4.
In the third sample, ρ("TTT", "TTT") = 27
문제풀이: 가장 많은 자모의 개수 x를 구한다.정답은 x^n입니다.
Code:
#include
#include
#include
#include
#include
#include
#define mod 1000000007
#define ll long long
using namespace std;
int ans,mx,n,num[30];
char ch[100005];
ll power(ll a,ll b)
{
ll ans=1;a%=mod;
for(ll i=b;i;i>>=1,a=a*a%mod)
if(i&1)ans=ans*a%mod;
return ans;
}
int main()
{
scanf("%d",&n);
scanf("%s",ch+1);
for(int i=1;i<=n;i++)
{
num[ch[i]-'A'+1]++;
mx=max(mx,num[ch[i]-'A'+1]);
}
for(int i=1;i<=26;i++)
if(num[i]==mx)ans++;
printf("%I64d
",power(ans,n));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.