luoguP4503 [CTSC2014]企鹅QQ hash

luoguP4503 [CTSC2014]企鹅QQ hash

既然只有一位的不同,那么我们可以枚举这一位....

我们只需要快速地计算去掉某一位的$hash$值....

由于$hash(S) = \sum s[i] * seed^i$,因此去掉第$i$位的权值只需要用$hash(S) - s[i] * seed^i$

由于字符串两两不相同,因此不存在两个串去掉$i$和去掉$j$仍会保持相似

这样子就可以做到不重的统计

复杂度$O(nL \log n)$

应该是可以用基排优化到$O(nL)$的...

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define ll long long
#define ri register int
#define ull unsigned long long
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)
#define drep(io, ed, st) for(ri io = ed; io >= st; io --)
#define gc getchar
inline int read() {
int p = ; char c = gc();
while(c > '' || c < '') c = gc();
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p;
} const int seed = ;
const int sid = ;
const int pid = ; int n, L, S;
char s[sid][pid];
ull wei[sid], val[sid], q[sid]; int main() {
n = read(); L = read(); S = read();
wei[] = ;
rep(i, , L) wei[i] = wei[i - ] * seed; rep(i, , n) {
scanf("%s", s[i] + );
rep(j, , L) val[i] += s[i][j] * wei[j];
} ll ans = ;
rep(i, , L) {
rep(j, , n)
q[j] = val[j] - s[j][i] * wei[i];
sort(q + , q + n + );
for(ri i = , j = ; i <= n; i = j + ) {
j = i;
while(q[j + ] == q[i]) j ++;
ans += (j - i + ) * (j - i) / ;
}
} printf("%lld\n", ans);
return ;
}
上一篇:VS2013 类向导 "异常来自 HRESULT:0x8CE0000B" 解决方法


下一篇:搭建自己的PHP框架心得——转载