Balala Power!
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 4124 Accepted Submission(s): 1004
Problem 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 109+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 nextlines contains a string si consisting of only lower case letters. (1≤|si|≤100000,∑|si|≤106)
For each test case, the first line contains one positive integers n, the number of strings. (1≤n≤100000)
Each of the nextlines contains a string si consisting of only lower case letters. (1≤|si|≤100000,∑|si|≤106)
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
Source
题意：给出一些字符串，由小写字母构成，用26（0-25）进制的数代替字母，不同字母不能相同。求转化后的26进制数最大为多少，结果对1e9+7取模。长度大
于1的串结果不能有前导0，除了单个字符.
【思路】：统计每个字符所在位，和其中的个数，以a字符为例。统计结果为
a[0]26^0+a[1]26^1+a[2]x2+.....+a[n-1]26^(n-1),其中a[i]代表a在第i位出现的次数
转化使得a[i]<26，变成x[0]26^0+x[1]26^1+...+x[n-1]26^(n-1)+x[n]26^(n)+...,
每个字符如此操作，谁取得最高位，这个字符就为25，第二高位为24，......，
排个序就可以了。如果出现前导0，从排序好的序列，从前往后找到可以为0的第一个字符，因为能作为0，它的x[i]26^(i)要越小，结果越大
于1的串结果不能有前导0，除了单个字符.
【思路】：统计每个字符所在位，和其中的个数，以a字符为例。统计结果为
a[0]26^0+a[1]26^1+a[2]x2+.....+a[n-1]26^(n-1),其中a[i]代表a在第i位出现的次数
转化使得a[i]<26，变成x[0]26^0+x[1]26^1+...+x[n-1]26^(n-1)+x[n]26^(n)+...,
每个字符如此操作，谁取得最高位，这个字符就为25，第二高位为24，......，
排个序就可以了。如果出现前导0，从排序好的序列，从前往后找到可以为0的第一个字符，因为能作为0，它的x[i]26^(i)要越小，结果越大
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdlib> 6 #include<string.h> 7 #include<set> 8 #include<vector> 9 #include<queue> 10 #include<stack> 11 #include<map> 12 #include<cmath> 13 typedef long long ll; 14 typedef unsigned long long LL; 15 using namespace std; 16 const double PI=acos(-1.0); 17 const double eps=0.0000000001; 18 const int N=100000+100; 19 const ll mod=1e9+7; 20 ll num[50][N]; 21 ll sum[N]; 22 ll val[N]; 23 int vis[N]; 24 int a[N]; 25 int t; 26 void init(){ 27 val[1]=1; 28 for(int i=2;i<=N;i++){ 29 val[i]=val[i-1]*26%mod; 30 } 31 } 32 bool cmp(int a,int b){ 33 for(int i=t-1;i>=1;i--){ 34 if(num[a][i]!=num[b][i]) 35 return num[a][i]<num[b][i]; 36 } 37 } 38 int main(){ 39 int n; 40 int tt=1; 41 init(); 42 string s; 43 while(scanf("%d",&n)!=EOF){ 44 t=0; 45 memset(vis,0,sizeof(vis)); 46 memset(num,0,sizeof(num)); 47 memset(sum,0,sizeof(sum)); 48 for(int i=1;i<=n;i++){ 49 cin>>s; 50 int len=s.size(); 51 if(len>1){ 52 vis[s[0]-'a']=1; 53 } 54 for(int j=0;j<len;j++){ 55 num[s[j]-'a'][len-j]++; 56 sum[s[j]-'a']+=val[len-j]; 57 sum[s[j]-'a']%=mod; 58 } 59 t=max(t,len); 60 } 61 for(int i=0;i<26;i++){ 62 for(int j=1;j<=t;j++){ 63 num[i][j+1]+=num[i][j]/26; 64 num[i][j]%=26; 65 } 66 t++; 67 while(num[i][t]){ 68 num[i][t+1]+=num[i][t]/26; 69 num[i][t++]%=26; 70 } 71 a[i]=i; 72 73 } 74 sort(a,a+26,cmp); 75 int flag; 76 for(int i=0;i<26;i++){ 77 if(vis[a[i]]==0){ 78 flag=a[i]; 79 break; 80 } 81 } 82 ll ans=0; 83 int x=25; 84 for(int i=25;i>=0;i--){ 85 if(a[i]!=flag){ 86 ans=ans+((x--)*sum[a[i]]%mod); 87 ans=ans%mod; 88 } 89 } 90 printf("Case #%d: %d ",tt++,ans); 91 } 92 }