题目大意:
定义字符串的hash值\(h = \sum_{i=0}^{n-1}p^{n-i-1}s_i\)
现在给定K个长度不超过L的字符串S,对于每个字符串S,求字典序最小长度不超过L的字符串T使得T不同于S但是Hash值相同.\(P\leq 2^{31},L \leq 8,K \leq 15\)
题解:
我们考虑直接爆搜\(O(26^L)\)
肯定过不了啊。。。
但是我们发现,如果我们枚举前L-1位,那么最后一位可以直接计算出来.
所以可以做到\(O(26^{L-1})\)
我们再进一步,如果我们枚举前L-4位,后4位我们打表预处理出来。
可以做到\(O(26^(L-4)log26^4)\)
我们发现这个复杂度妥妥地能过。
但是嘛。。。也许是我写丑了。。。本地跑的特别慢但是bzoj能A…
这道题就是个大毒瘤,写了一下午！
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
inline void read(uint &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 22;
uint P,L,K,n;
char ss[26*26*26*26 + 26*26*26 + 26*26 + 26 + 10][6];
uint cnt = 0;
inline uint qpow(uint x,uint p){
uint ret = 1;
for(;p;x=x*x,p>>=1) if(p&1) ret=ret*x;
return ret;
}
char s[maxn];
inline uint hash(char *s,uint n){
uint ret = 0;
for(uint i=0;i<n;++i){
ret += (uint)s[i]*qpow(P,n-i-1);
}
return ret;
}
uint val;bool flag;
char t[maxn];uint len;
char ans[maxn];
inline void judge(uint m){
bool cp = false;
if(n != m) cp = true;
else for(uint i=0;i<n;++i) if(s[i] != t[i]) cp = true;
if(!cp) return;
if(hash(t,m) == val){
if(!flag){
flag = true;len = m;
for(uint i = 0;i<len;++i){
ans[i] = t[i];
}
}else{
bool sw = false;
for(uint i = 0;i<len && i < m;++i){
if(t[i] < ans[i]){
sw = true;
break;
}
}
if(sw || (!sw && m < len)){
for(uint i=0;i<m;++i){
ans[i] = t[i];
}len = m;
}
}
}
}
inline void judge(char* t){
int m = strlen(t);
bool cp = false;
if(n != m) cp = true;
else for(uint i=0;i<n;++i) if(s[i] != t[i]) cp = true;
if(!cp) return;
if(hash(t,m) == val){
if(!flag){
flag = true;len = m;
for(uint i = 0;i<len;++i){
ans[i] = t[i];
}
}else{
bool sw = false;
for(uint i = 0;i<len && i < m;++i){
if(t[i] < ans[i]){
sw = true;
break;
}
}
if(sw || (!sw && m < len)){
for(uint i=0;i<m;++i){
ans[i] = t[i];
}len = m;
}
}
}
}
inline void calc(uint m){
uint x = hash(t,m);
x = x*P;
uint y = val - x;
t[m] = y;
if(y >= 'A' && y <= 'Z')judge(m+1);
}
void dfs(uint pos){
if(pos == L-1){
calc(pos);
return;
}
for(char ch='A';ch<='Z';++ch){
t[pos] = ch;
dfs(pos+1);
if(flag) return;
judge(pos);
if(flag) return;
}
}
char tmp[6];
map<int,int>mp2,mp3,mp4;
char query[maxn][maxn];
inline void save4(){
uint h = hash(tmp,4);
if(mp4[h] == 0){
for(uint i=1;i<=K;++i){
if(!strcmp(tmp,query[i]))
return;
}
++cnt;
for(uint i=0;i<4;++i){
ss[cnt][i] = tmp[i];
}
mp4[h] = cnt;
}
}
inline void save3(){
uint h = hash(tmp,3);
if(mp3[h] == 0){
for(uint i=1;i<=K;++i){
if(!strcmp(tmp,query[i]))
return;
}
++cnt;
for(uint i=0;i<3;++i){
ss[cnt][i] = tmp[i];
}
mp3[h] = cnt;
}
}
inline void save2(){
uint h = hash(tmp,2);
if(mp2[h] == 0){
for(uint i=1;i<=K;++i){
if(!strcmp(tmp,query[i]))
return;
}
++cnt;
for(uint i=0;i<2;++i){
ss[cnt][i] = tmp[i];
}
mp2[h] = cnt;
}
}
inline void dfss(uint pos){
if(pos == 2) save2();
if(pos == 3) save3();
if(pos == 4){
save4();
return ;
}
for(char ch = 'A';ch<='Z';++ch){
tmp[pos] = ch;
dfss(pos+1);
}
}
inline void ca4(uint m){
uint x = hash(t,m);
x = x*P*P*P*P;
uint y = val - x;
for(int i=1;i<=K;++i){
if(strlen(query[i]) == 4){
for(int j=0;j<4;++j){
t[m+j] = query[i][j];
}
judge(m+4);
}
}
if(mp4[y] == 0) return;
for(int i=0;i<4;++i){
t[m+i] = ss[mp4[y]][i];
}
judge(m+4);
}
inline void ca3(uint m){
uint x = hash(t,m);
x = x*P*P*P;
uint y = val - x;
for(int i=1;i<=K;++i){
if(strlen(query[i]) == 3){
for(int j=0;j<3;++j){
t[m+j] = query[i][j];
}
judge(m+3);
}
}
if(mp3[y] == 0) return;
for(int i=0;i<3;++i){
t[m+i] = ss[mp3[y]][i];
}
judge(m+3);
}
inline void ca2(uint m){
uint x = hash(t,m);
x = x*P*P;
uint y = val - x;
for(int i=1;i<=K;++i){
if(strlen(query[i]) == 3){
for(int j=0;j<3;++j){
t[m+j] = query[i][j];
}
judge(m+3);
}
}
if(mp2[y] == 0) return;
for(int i=0;i<2;++i){
t[m+i] = ss[mp2[y]][i];
}
judge(m+2);
}
void search(uint pos){
if(pos == L-4){
calc(pos);
ca2(pos);
ca3(pos);
ca4(pos);
return;
}
for(char ch='A';ch<='Z';++ch){
t[pos] = ch;
search(pos+1);
if(flag) return;
judge(pos);
if(flag) return;
}
calc(pos);ca2(pos);ca3(pos);ca4(pos);
}
int main(){
read(P);read(L);read(K);
for(uint i=1;i<=K;++i) scanf("%s",query[i]);
dfss(0);
for(uint i=1;i<=K;++i){
n = strlen(query[i]);
for(uint j=0;j<n;++j) s[j] = query[i][j];
val = hash(s,n);
flag = false;
if(L <= 4) dfs(0);
else search(0);
if(flag) ans[len] = 0,printf("%s\n",ans);
else puts("-1");
}
getchar();getchar();
return 0;
}
