[CF 521A] DNA Alignment

作法：

對於原題定義的式子，最外層的 sigma 可以先拿掉，因為不管 i 是多少，當 j 跑一圈後算出來的值都會一樣。再來則是注意到一個字母會被算到幾次，會發現每個在 s 裡的字母都會被算到「在 t 裡面且和他一樣的字母個數」那麼多個。所以如果 s 裡的 A,C,G,T 分別有 a,b,c,d 個，並設我們要找的 t 的四個字母分別有 x,y,z,w 個，所以我們要讓當 x+y+z+w = 定值(字串長度) 的時候， ax + by + cz + dw 的值最大。這邊就可以用調整法，如果 a,b,c,d 裡面有一個數嚴格小於另一個數，那小的那個乘的數可以直接把他往下調成 0 ，大的那個乘的數往上調，會讓整體的解更佳。所以重點只剩下那些出現次數最多的字母們了，而可以發現怎麼取都可以達到最大值，也就是在要求的 t 的每一位都可以任意放那些字母，也就是如果出現次數最多的字母有 k 個，那麼答案就是 k^n ，其中 n 是字串長度。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
 
LL power(LL x,int n)
{
    if(n==0) return 1LL ;
    if(n==1) return x ;
    LL tmp=power(x,n/2) ;
    if(n%2) return (tmp*tmp%MOD)*x%MOD ;
    else return tmp*tmp%MOD ;
}
 
char s[100000+10] ;
int a[4] ;
main()
{
    int n ; scanf("%d%s",&n,s) ;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='A') a[0]++ ;
        if(s[i]=='C') a[1]++ ;
        if(s[i]=='G') a[2]++ ;
        if(s[i]=='T') a[3]++ ;
    }
    int M=max(max(a[0],a[1]),max(a[2],a[3])) ;
    int num=0 ;
    for(int i=0;i<4;i++) if(a[i]==M) num++ ;
    printf("%I64d\n",power(num,n)) ;
}