单词分类

【题目描述】

当组成这两个单词的各个字母数量均相等时，这两个单词可以分为一类。

例如“AABAC”和“CBAAA”归为一类，和“AAABB”不是一类。

现有N个单词，所有单词均由大写字母组成，每个单词的长度不超过100，询问这些单词会被分成几类。

【输入描述】

第一行输入一个数；

接下来N行，每行输入一个单词。

【输出描述】

输出一个数，表示答案。

【样例输入】

3

AABAC

CBAAA

AAABB

【样例输出】

2

【数据范围及提示】

对于70%的数据，N ≤ 100；

对于100%的数据，N ≤ 10000。

源代码：

#include<cstdio>
#include<cstring>
#define INF1 1000007
#define INF2 10003
struct Node
{
    int T1,T2;
}i[10001];
int n,Num(0),Prime[26];
void Euler() //欧拉筛法。
{
    int Num(0);
    bool f[102]={0};
    for (int a=2;a<102;a++)
    {
        if (!f[a])
          Prime[Num++]=a;
        for (int b=0;b<Num&&a*Prime[b]<102;b++)
        {
            f[a*Prime[b]]=true;
            if (!(a%Prime[b]))
              break;
        }
    }
}
int main() //一言不合双Hash。
{
    Euler();
    scanf("%d",&n);
    getchar();
    for (int a=0;a<n;a++)
    {
        char S[101];
        bool T(0);
        gets(S);
        int Sum1=1,Sum2=1,Length=strlen(S);
        for (int a=0;a<Length;a++)
          Sum1=(Sum1*Prime[S[a]-'A'])%INF1;
        for (int a=0;a<Length;a++) //妈的最后一个点被卡了，那就双Hash，你不是很能吗。
          Sum2=(Sum2*Prime[S[a]-'A'])%INF2;
        for (int a=1;a<=Num;a++)
          if (Sum1==i[a].T1&&Sum2==i[a].T2)
          {
            T=true;
            break;
          }
        if (!T)
        {
            i[++Num].T1=Sum1;
            i[Num].T2=Sum2;
        }
    }
    printf("%d",Num);
    return 0;
}