# HDU 6034 Balala Power! （贪心）

## Description

Talented Mr.Tang has n strings consisting of only lower case characters. He wants to charge them with Balala Power (he could change each character ranged from a to z into each number ranged from 0 to 25, but each two different characters should not be changed into the same number) so that he could calculate the sum of these strings as integers in base 26 hilariously.

Mr.Tang wants you to maximize the summation. Notice that no string in this problem could have leading zeros except for string “0”. It is guaranteed that at least one character does not appear at the beginning of any string.

The summation may be quite large, so you should output it in modulo 10^9+7.

## Input

The input contains multiple test cases.

For each test case, the first line contains one positive integers n, the number of strings. (1≤n≤100000)

Each of the next n lines contains a string si consisting of only lower case letters. (1≤|si|≤100000,∑|si|≤10^6)

## Output

For each test case, output “Case #x: y” in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.

## Sample Input

1
a
2
aa
bb
3
a
ba
abc


## Sample Output

Case #1: 25
Case #2: 1323
Case #3: 18221


## 题意

n 个字符串，我们可以把串中任意一个字母替换成 0-25 这些数字中的一个，要求不同的字母不可以替换为相同的数字，问最终组成的所有 26 进制数的最大和。

## 思路

It is guaranteed that at least one character does not appear at the beginning of any string.

## AC 代码

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;

typedef __int64 LL;
const int maxs=26;
const int maxn = 1e5+10;
const int mod = 1e9+7;

struct node
{
int data;
int num[maxn];      //所有字符串中该字母在第i位中出现过多少次
} ks[maxs];
bool vis[maxs];         //该字母是否在长度大于1的字符串首位出现过
char str[maxn];

bool cmp(const node &a,const node &b)   //比较两个26进制数的大小
{
for(int i=maxn-1; i>=0; i--)
if(a.num[i]!=b.num[i])
return a.num[i]<b.num[i];
return false;
}

void init()
{
for(int i=0; i<maxs; i++)
{
ks[i].data=i;
memset(ks[i].num,0,sizeof(ks[i].num));
}
memset(vis,false,sizeof(vis));
}

int main()
{
ios::sync_with_stdio(false);
int n;
for(int ti=1; cin>>n; ti++)
{
init();
for(int i=0; i<n; i++)
{
cin>>str;
int len=strlen(str);
if(len>1)vis[str[0]-'a']=true;
for(int j=0; j<len; j++)
{
int cr=str[j]-'a';
int rk=len-j-1;
ks[cr].num[rk]++;
while(ks[cr].num[rk]==maxs) //进位
{
ks[cr].num[rk++]=0;
ks[cr].num[rk]++;
}
}
}
sort(ks,ks+maxs,cmp);
int op=-1;
for(int i=0; i<maxs; i++)           //寻找一个没有在首位出现过的字母
if(vis[ks[i].data]==false)
{
op=i;
break;
}
LL ans=0;
for(int i=maxs-1; i>=0; i--)
{
LL cnt=0;
for(int j=maxn-1; j>=0; j--)
cnt=((cnt*maxs)%mod+ks[i].num[j])%mod;
ans=(ans+(cnt*(i==op?0:i<op?i+1:i))%mod)%mod;   //若权值比较小的字母在首位出现过，则用其他代替
}
cout<<"Case #"<<ti<<": "<<ans<<endl;
}
return 0;
}