你好！我是你的 OI 金牌教练。针对 P3370 【模板】字符串哈希，我们要设计一套既能卡掉低效算法，又能控制文件体积的数据。

核心设计逻辑

1. 体积控制（1MB 目标）：
   • 题目上限 $N=10000, M=1500$ 会产生约 15MB 的文件。为了将文件控制在 1MB 左右，我们将 $N$ 保持在 10000，但将总字符数（$\sum M_i$）限制在 $8 \times 10^5$ 左右。
   • $8 \times 10^5$ 字节 $\approx 0.76$ MB，非常理想。
2. 区分度设计：
   • $O(N^2 \cdot M)$ 暴力：在 $N=10000$ 时必死。
   • 单哈希碰撞测试：构造极度相似的字符串（如只差最后一个字符）来冲击弱哈希函数。
   • 全重复与全唯一：覆盖去重逻辑的边界。

数据生成器 (Generator.cpp)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

typedef unsigned long long ull;

// --- 双哈希求解器：用于生成标准 .out 数据 ---
struct HashPair {
    ull h1, h2;
    bool operator<(const HashPair& o) const {
        return h1 != o.h1 ? h1 < o.h1 : h2 < o.h2;
    }
    bool operator!=(const HashPair& o) const {
        return h1 != o.h1 || h2 != o.h2;
    }
};

void solve_and_write_out(string in_file, string out_file) {
    ifstream fin(in_file);
    ofstream fout(out_file);
    int n; fin >> n;
    vector<HashPair> list;
    const ull b1 = 131, b2 = 13331, m1 = 1e9 + 7, m2 = 1e9 + 9;
    for (int i = 0; i < n; ++i) {
        string s; fin >> s;
        ull r1 = 0, r2 = 0;
        for (char c : s) {
            r1 = (r1 * b1 + (ull)c) % m1;
            r2 = (r2 * b2 + (ull)c) % m2;
        }
        list.push_back({r1, r2});
    }
    sort(list.begin(), list.end());
    int ans = (n > 0) ? 1 : 0;
    for (int i = 1; i < n; ++i) if (list[i] != list[i - 1]) ans++;
    fout << ans << endl;
}

// --- 随机字符串生成工具 ---
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string gen_str(int len, string charset = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz") {
    string s = "";
    for (int i = 0; i < len; ++i) s += charset[rng() % charset.size()];
    return s;
}

void make_case(int id) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fout(in_name);

    if (id == 1) { // 样例数据
        fout << "5\nabc\naaaa\nabc\nabcc\n12345\n";
    } else {
        int n, m_max;
        if (id <= 3) { n = 100; m_max = 50; } // 30% 规模
        else if (id <= 6) { n = 1000; m_max = 150; } // 70% 规模
        else { n = 10000; m_max = 80; } // 100% 规模 (总字符约80万)

        fout << n << "\n";
        
        // 特殊构造逻辑
        if (id == 8) { // 全重复
            string s = gen_str(m_max);
            for (int i = 0; i < n; ++i) fout << s << "\n";
        } 
        else if (id == 9) { // 极度相似（卡弱哈希）
            string base = gen_str(m_max - 1);
            for (int i = 0; i < n; ++i) {
                // 仅最后一个字符不同
                fout << base << (char)('!' + (i % 90)) << "\n";
            }
        }
        else { // 混合随机
            vector<string> pool;
            for(int i=0; i<n/5; ++i) pool.push_back(gen_str(rng() % m_max + 1));
            for(int i=0; i<n; ++i) {
                if (rng() % 10 < 3) fout << pool[rng() % pool.size()] << "\n"; // 30%重复
                else fout << gen_str(rng() % m_max + 1) << "\n";
            }
        }
    }
    fout.close();
    solve_and_write_out(in_name, out_name);
    printf("Case %d Generated.\n", id);
}

int main() {
    for (int i = 1; i <= 10; ++i) make_case(i);
    return 0;
}

测试点规划说明 (OJ 部署标准)

教练的生成器优化心得

1. 文件大小计算：
   • 我们在 Case 7-10 选取了 $N=10000, M \approx 80$。
   • 估算：$10000 \times 80 = 800,000$ 字节 $\approx 781$ KB。
   • 加上换行符和 $N$ 的字符，文件刚好控制在 800KB - 900KB 之间，完美符合 1MB 内的要求。
2. 生成效率（剪枝思想）：
   • 在生成标准输出时，我们直接内置了一个 Double Hash + Sort 的 $O(NM)$ 求解器。
   • 这样生成 $10$ 个点的总耗时不超过 1 秒，远比手动运行两个程序要快。
3. 安全性（Exception Handling）：
   • 使用 n > 0 的判断规避了 $N=0$ 时的逻辑错误。
   • 哈希计算过程中使用 unsigned long long 配合 1e9+7 类的大质数，规避了溢出风险（除了预期的自然溢出）和除零异常。
4. 非递归写法：
   • 整个生成器和求解逻辑全部基于 for 循环和 while 循环，没有任何深度递归，确保不会爆掉系统栈。

教练寄语：在做字符串题目时，千万记得“双哈希保平安”。如果发现本地生成数据太慢，多半是频繁的字符串拷贝或 std::endl 导致的，改用 \n 和引用传递能让你的生成器飞起来！

你好！我是你的 NOI 金牌教练。字符串哈希（String Hash）是字符串处理算法的基石。在处理这道模板题时，我们的目标不仅是 AC，更要学习如何构造一个低冲突率、高执行效率的哈希系统。

在 NOI 竞赛中，单哈希（尤其是自然溢出）有时会被出题人构造的特殊数据“卡掉”。因此，我将为你展示最稳妥的**双哈希（Double Hash）**实现方案。

一、 题解标准代码 (C++14)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 题目：【模板】字符串哈希 (P3370)
 * 核心思路：双哈希 (Double Hash)
 * 
 * 为什么用双哈希？
 * 1. 单哈希（如只对 2^64 取模）存在哈希碰撞风险，容易被构造数据卡掉。
 * 2. 双哈希通过两组不同的底数(Base)和模数(Mod)，极大地降低了碰撞概率。
 *    碰撞概率约为 1 / (Mod1 * Mod2)，在 10^18 级别，几乎不可能在竞赛中撞车。
 */

typedef unsigned long long ull;

// 定义两组不同的哈希参数
// 底数通常选取大于字符集大小（本题约62）的质数
const ull base1 = 131;
const ull base2 = 13331;

// 模数选取大质数。也可以一组用大质数，一组用 ull 自然溢出
const ull mod1 = 1e9 + 7;
const ull mod2 = 1e9 + 9;

// 存储双哈希结果的结构体
struct HashPair {
    ull h1, h2;
    // 重载小于运算符，用于 std::sort
    bool operator<(const HashPair& other) const {
        if (h1 != other.h1) return h1 < other.h1;
        return h2 < other.h2;
    }
    // 重载等于运算符，用于去重判断
    bool operator!=(const HashPair& other) const {
        return h1 != other.h1 || h2 != other.h2;
    }
};

int main() {
    // 1. 快速 I/O 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    vector<HashPair> hash_list;
    hash_list.reserve(n); // 预分配内存，减少 vector 扩容开销

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;

        ull res1 = 0, res2 = 0;
        // 2. 计算滚动哈希 (Polynomial Rolling Hash)
        for (char c : s) {
            // 关键点：哈希公式 (h * base + char) % mod
            res1 = (res1 * base1 + (ull)c) % mod1;
            res2 = (res2 * base2 + (ull)c) % mod2;
        }
        hash_list.push_back({res1, res2});
    }

    // 3. 排序哈希值
    // 排序后，相同的字符串其哈希值必然相邻
    sort(hash_list.begin(), hash_list.end());

    // 4. 统计不同哈希值的个数
    int ans = 0;
    if (n > 0) {
        ans = 1; // 只要有数据，至少有一个不同的串
        for (int i = 1; i < n; ++i) {
            // 易错点：必须通过双哈希值同时判断
            if (hash_list[i] != hash_list[i-1]) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度分析

• 哈希计算阶段：
  • 我们需要遍历 $N$ 个字符串，每个字符串平均长度为 $M_{avg}$。
  • 每个字符的处理是常数级的（两次乘法、两次加法、两次取模）。
  • 复杂度：$O(N \cdot M_{avg})$。
• 排序与统计阶段：
  • 对 $N$ 个双哈希对进行排序，复杂度：$O(N \log N)$。
  • 遍历统计：$O(N)$。
• 总复杂度：$O(NM + N \log N)$。
  • 代入数据：$10^4 \cdot 1500 + 10^4 \cdot \log(10^4) \approx 1.5 \times 10^7 + 1.3 \times 10^5$。
  • 在 1.0s 的时限内非常充裕，甚至可以处理 $N=10^5$ 量级的数据。

2. 空间复杂度分析

• 主要存储开销：vector<HashPair> 存储了 $N$ 个双哈希对。
• 每个 HashPair 包含两个 ull（16字节），总空间：$10^4 \times 16 \text{ Bytes} \approx 160 \text{ KB}$。
• 字符串读取：每次读取一个字符串到局部变量，最大占用 $1500 \text{ Bytes}$。
• 结论：远低于 128MB 的限制，空间利用极其高效。

三、 时间复杂度优化建议

1. 自然溢出 (Natural Overflow)：
   • 可以将其中一组模数设为 $2^{64}$（即直接使用 unsigned long long 不取模）。CPU 对自然溢出的处理比 % 运算快得多。
2. 自定义哈希表 (Unordered Set)：
   • 如果 $N$ 极大（如 $10^6$）而 $M$ 较小，可以使用 std::unordered_set 配合自定义哈希函数。平均时间复杂度可降至 $O(NM)$。
3. Trie 树（字典树）：
   • 对于字符串去重，Trie 树在理论上可以做到 $O(NM)$。但在本题 $M=1500$ 且字符集较大的情况下，Trie 树的指针开销非常大，极易导致内存超限 (MLE) 或缓存不命中 (Cache Miss) 导致的性能下降。

四、 易错点与教练提示

1. 底数 (Base) 的选取：
   • 底数必须大于字符集中最大的字符编码。例如本题包含数字和字母，'z' 的 ASCII 是 122，底数取 131 是安全的。
2. 模数 (Mod) 的选取：
   • 模数必须是大质数。如果你只用一个模数（单哈希），推荐使用 1000000000000037LL (10^15 级别) 或更大的数。
3. 0 字符问题：
   • 如果字符串中包含编号为 0 的字符，哈希公式 h = h * base + 0 会导致前导零失效（如 \0ab 和 ab 的哈希值可能相同）。在处理复杂字符集时，通常建议给字符编码统一加 1，即 (ull)c + 1。
4. Hash Killer：
   • 拓展阅读中提到的 Hash Killer 是指针对特定的模数构造冲突。双哈希是解决这一问题的终极武器。在 NOI 现场赛中，除非万不得已，否则不建议只用单哈希。

你好！我是你的 NOI 金牌教练。字符串哈希（String Hash）是信息学奥赛中处理字符串匹配、去重、判等问题的“瑞士军刀”。在更高级的题目（如后缀自动机或 KMP 的替代方案）中，哈希也是重要的优化手段。

下面我将为你解析 P3370 【模板】字符串哈希。

一、 预备知识点

1. 多项式滚动哈希 (Polynomial Rolling Hash)：将字符串看作一个 $P$ 进制数，计算其对 $Q$ 取模后的值。公式：$H(s) = (\sum s[i] \times P^{len-1-i}) \pmod Q$。
2. 进制底数 $P$ 的选择：通常选取一个大于字符集大小的质数（如 31, 131, 13331）。
3. 模数 $Q$ 与冲突处理：
   • 单哈希：常取 $10^9+7$ 或 $10^9+9$。容易被特定构造数据“卡掉”（见拓展阅读中的 Hash Killer 系列）。
   • 自然溢出：利用 unsigned long long 的特性，相当于对 $2^{64}$ 取模。
   • 双哈希：用两组不同的 $P, Q$ 计算，只有两组哈希值都相等才判定字符串相同。
4. 排序与去重：将所有哈希值存入数组，通过 std::sort 排序后，统计相邻且不相等的值。

二、 教学启发与草稿纸推理过程

1. 启发式提问

• 教练问：直接用 std::string 放入 std::set 去重行吗？复杂度是多少？
• 学生答：可以，但 set 比较字符串时是 $O(M)$ 的。总复杂度 $O(N \cdot M \cdot \log N)$。当 $N=10^4, M=1500$ 时，大约 $2 \times 10^8$ 次运算，勉强通过，但如果是 $N=10^5$ 就必挂。
• 教练问：我们能不能把字符串变成一个整数，通过比较整数来代替比较字符串？

2. 草稿纸模拟 (哈希过程)

假设字符串为 abc，取 $P=131, Q=2^{64}$ (自然溢出)：

1. 字符 'a' 的 ASCII 为 97。$H = 97$。
2. 读入 'b' (98)。$H = 97 \times 131 + 98 = 12805$。
3. 读入 'c' (99)。$H = 12805 \times 131 + 99 = 1677554$。 最终 abc 对应整数 1677554。

3. 复杂度分析思考过程

• 时间复杂度：
  • 计算 $N$ 个哈希值：每个长度为 $M$，共 $O(N \cdot M)$。
  • 排序哈希值：$O(N \log N)$。
  • 去重计数：$O(N)$。
  • 总计：$O(NM + N \log N)$。在 $100\%$ 数据下约 $1.5 \times 10^7$ 次运算，非常安全。
• 空间复杂度：
  • 存储所有哈希值：$O(N)$，即 $10000 \times 8 \text{ 字节} \approx 80 \text{ KB}$。

三、 算法流程图 (Mermaid 语法)

graph TD
    A("开始 (Start)") --> B("读取 N")
    B --> C("循环 i 从 1 到 N")
    C --> D("读取字符串 S")
    D --> E("初始化 HashValue = 0")
    E --> F("逐个读取 S 中的字符 c")
    F --> G("HashValue = HashValue * 131 + c")
    G -- "遍历结束" --> H("将 HashValue 存入数组 List")
    H --> I("i 增加 1")
    I --> C
    C -- "循环结束" --> J("对 List 数组进行升序排序 (Sort)")
    J --> K("初始化 Ans = 1, j = 1")
    K --> L("j 从 1 遍历到 N-1")
    L --> M{"List(j) 是否不等于 List(j-1)?"}
    M -- "是" --> N("Ans 增加 1")
    M -- "否" --> O("继续")
    N --> P("j 增加 1")
    O --> P
    P --> L
    L -- "遍历结束" --> Q("输出结果 Ans")
    Q --> R("结束 (End)")

四、 NOI 竞赛格式题目复述

【模板】字符串哈希

【问题描述】 给定 $N$ 个字符串（包含数字、大小写字母，大小写敏感），请求出这 $N$ 个字符串中共有多少个不同的字符串。

【输入格式】 第一行包含一个整数 $N$，表示字符串的个数。 接下来 $N$ 行，每行包含一个字符串。

【输出格式】 输出包含一个整数，为不同的字符串个数。

【输入输出样例 #1】 输入：

5
abc
aaaa
abc
abcc
12345

输出：

4

【数据范围】

• 对于 30% 的数据：$N \le 10$，$M_{max} \le 15$。
• 对于 100% 的数据：$N \le 10000$，$M_i \approx 1000$，$M_{max} \le 1500$。

五、 读题关键点总结

1. “不同的字符串个数”：这是典型的去重计数问题，哈希或字典树 (Trie) 是首选。
2. “大小写敏感”：计算哈希时不需要进行统一大小写转换（如 tolower）。
3. “包含数字、字母”：字符集大小约为 $10 + 26 + 26 = 62$。进制底数 $P$ 必须大于 62，取 131 或 13331 非常稳妥。
4. 拓展阅读中的“Hash Killer”：这是在提醒你，单哈希（尤其是模数较小时）存在被碰撞的风险。在 NOI 竞赛中，双哈希或自然溢出+特定的底数是更稳健的选择。

六、 数据生成器 (Generator.cpp)

用于生成符合 NOI 规范的测试数据，特别包含重复字符串以测试去重逻辑。

#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <chrono>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

string gen_rand_str(int len) {
    const string charset = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    string res = "";
    for(int i = 0; i < len; ++i) {
        res += charset[rng() % charset.size()];
    }
    return res;
}

int main() {
    int N = 10000;
    cout << N << endl;
    
    vector<string> pool;
    // 先生成一部分作为“种子”字符串，后续用来制造重复
    for(int i = 0; i < 2000; ++i) {
        pool.push_back(gen_rand_str(rng() % 500 + 500));
    }

    for(int i = 0; i < N; ++i) {
        if(rng() % 10 < 3) { 
            // 30% 的概率产生重复字符串
            cout << pool[rng() % pool.size()] << "\n";
        } else {
            // 70% 的概率产生全新字符串
            cout << gen_rand_str(rng() % 1000 + 500) << "\n";
        }
    }
    return 0;
}

教练点评：字符串哈希的精髓在于“化繁为简”。掌握了它，你就掌握了在 $O(1)$ 时间内比较任意长字符串的魔法。但在正式比赛中，请务必考虑双哈希以防万一。加油！