哈希

给定3个长度为n的字符串A,B,C.现在需要构造出一个字符串S，S[i]可以是A[i],B[i],C[i]中的一个。S的哈希值，由以下代码生成：

function hash(S):
answer = 0
for each valid index i into S, starting from 0:
answer = (answer * 127 + ord(S[i])) mod 1000000000000037
return answer

ord(S[i])表示S[i]的ascii码值。

输入描述:

第一行有一个正整数n，表示字符串的长度，n≤20。
接下来3行，表示字符串A,B,C。

输出描述:

输出最小的哈希值

示例1
输入

4
ELLY
KRIS
STAN

输出

142572564

haxi.cppview raw

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL num[5000005],ans;
LL P=1000000000000037LL,T;
string a,b,c;
int all,n,m,tot;
void dfs(int x,LL p){
    if(x==n){
        num[tot]=p;
        for(int i=0;i<m;i++)num[tot]=(num[tot]*127)%P;
        tot++;
        return;
    }
    dfs(x+1,(p*127+a[x])%P);
    dfs(x+1,(p*127+b[x])%P);
    dfs(x+1,(p*127+c[x])%P);
}
void DFS(int x,LL p){
    if(x==all){
        LL tmp=(num[0]+p)%P;
        ans=min(ans,tmp);
        int k=lower_bound(num,num+tot,P-p)-num;
        if(k!=tot)ans=min(ans,(num[k]+p)%P);
        return;
    }
    DFS(x+1,(p*127+a[x])%P);
    DFS(x+1,(p*127+b[x])%P);
    DFS(x+1,(p*127+c[x])%P);
}
int main() {
        int N;string A,B,C;
        cin>>N>>A>>B>>C;
        n=N/2;all=N;
        m=N-n;
        tot=0;
        a=A;b=B;c=C;
        dfs(0,0);
        sort(num,num+tot);
        ans=P;
        DFS(n,0);
        cout<< ans <<endl;
};