题解 P3370 【【模板】字符串哈希】

mrkrnblsa · 2017-05-06 22:06:11 · 题解

在疯狂地用线性筛法筛除N多素数后，终于发现了一个神奇的数字：33951943，位数只有8位不会卡内存2333

具体对这个数字的利用看代码2333（只把输入的一个字符串的每个字符的ascll码乘在一起在%33951943就行了2333）

pra\

gma GCC optimize ("O3")
#include<stdio.h>
using namespace std;
int n,ans;
unsigned int now=1;
bool s[33951943];
char a[2000];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%s",&a);
        for(int j=0;a[j];++j){
            now*=a[j];//把每个字符乘起来
            now%=33951943;//%一下就可以啦2333
        }
        if(!s[now]){
            ++ans;
            s[now]=1;
        }
        now=1;
    }
    printf("%d",ans);
    return 0;
}