C. DNA Alignment
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 stringssandthave the same lengthn, then the functionh(s,t)is defined as the number of positions in which the respective symbols ofsandtarethe same. Functionh(s,t)can be used to define the function of Vasya distanceρ(s,t):
whereis obtained from strings, by applying left circular shiftitimes. 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 stringsof lengthnon the Internet. Now he wants to count how many stringstthere are such that the Vasya distance from the stringsattains maximum possible value. Formally speaking,tmust 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 modulo109+7.
Input
The first line of the input contains a single integern(1≤n≤105).
The second line of the input contains a single string of lengthn, consisting of characters"ACGT".
Output
Print a single number— the answer modulo109+7.
Sample test(s)
input
1C
output
1
input
2AG
output
4
input
3TTT
output
1
Note
Please note that if for two distinct stringst1andt2valuesρ(s,t1)иρ(s,t2)are maximum among all possiblet, 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 stringstof 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
算是一道数学题，，理解那个公式非常重要。题目意思是 知道s 求 使ρ(s,t) 最大的t有多少种。 很显然，根据公式要最大，t 中的字母应该只含有 s 中出现最多的字母。例如s 为 AATTC，那么t 可以为AAAAA TTTTT AATTT AAAAT。。。。。。等等。所以根据排列组合的原理t 的种数为 s种出现最多的字母的个数 p的n次幂
package com.codeforces.algorithm;import java.util.*;public class DNAAlignment {private static long pow(int a,int b,int mod){long ret =1,x=a;while(b!=0){if((b&1)!=0) ret=(ret*x)%mod;x=(x*x)%mod;b>>=1;}return ret;}public static int match(char c){if(c=='A') return 0;if(c=='C') return 1;if(c=='G') return 2;if(c=='T') return 3;return -1;}public static void main(String []args){@SuppressWarnings("resource")Scanner cin = new Scanner(System.in);final int MOD = 1000000007;while(cin.hasNext()){int n = cin.nextInt();int []num = new int [4];for(int i=0;i<num.length;i++) num[i]=0;String str = cin.next();for(int i=0;i<str.length();i++){num[match(str.charAt(i))]++;}Arrays.sort(num);int p=1;for(int i=0;i<3;i++){if(num[i]==num[3]) p++;}//System.out.println(p+" "+n);System.out.println(pow(p,n,MOD));}}}
与其在那里苦苦挣扎，碍于面子硬撑，倒不如微笑着面对，
