题解 | #大整数哈希#

题目链接

大整数哈希

题目描述

给定初始映射 f: [0, 2^64) → [0, 2^64)，对任意 x 初始 f(x) = 0。

共有 n 次操作，对于第 i 次操作（从 1 到 n），会给定一对整数 (x, y)，执行：

记录 ans_i = f(x) 的当前值。
更新映射：f(x) = y。

要求计算最终的总和： $\sum_{i=1}^{n} i \times ans_i \pmod{2^{64}}$

这是一个 ACM 模式 的题目，你需要处理标准输入和输出。

输入描述: 第一行包含一个整数 n ( $1 \le n \le 5 \times 10^6$ )。接下来的 n 行，每行包含两个整数 x, y ( $0 \le x, y < 2^{64}$ )。

输出描述: 输出一个整数，表示 $\sum_{i=1}^{n} i \times ans_i \pmod{2^{64}}$ 的结果。

示例: 输入:

输出:

说明:

第1次 (i=1): 操作 (1, 5)。ans_1 = f(1)，初始为 0。总和 += 1 * 0。更新 f(1) = 5。
第2次 (i=2): 操作 (2, 4)。ans_2 = f(2)，初始为 0。总和 += 2 * 0。更新 f(2) = 4。
第3次 (i=3): 操作 (1, 7)。ans_3 = f(1)，当前为 5。总和 += 3 * 5。更新 f(1) = 7。
最终总和 = 0 + 0 + 15 = 15。

解题思路

这道题的核心是模拟一个可以动态更新的函数 f，并累加一个带权重的和。关键点在于处理巨大的数据范围。

x 和 y 的范围达到了 [0, 2^64)，这意味着我们必须使用64位无符号整数来存储它们。普通32位 int 会导致数据溢出。

最适合的数据结构是 哈希表（在 C++ 中是 unordered_map，Java 中是 HashMap，Python 中是 dict）。

算法步骤:

初始化一个哈希表 f_map，键和值的类型都应为64位整型。
初始化一个64位整型变量 total_sum = 0。
读取操作次数 n。
使用一个循环，从 i = 1 迭代到 n： a. 读取当次操作的64位整数 x 和 y。 b. 查询 f(x): 在 f_map 中查找键 x。如果不存在，其值默认为 0。 c. 累加总和: 计算 i * f(x) 并加到 total_sum 上。 d. 更新映射: 在 f_map 中设置 f_map[x] = y。
循环结束后，输出 total_sum。

语言实现细节:

C++: 使用 unsigned long long 类型。该类型的算术运算在溢出时会自动对 2^64 取模，这正是题目要求。
Java: long 类型是64位有符号整数，无法存储大于 $2^{63}-1$ 的输入值 x 和 y。此外，中间的累加和 totalSum 也会远超 long 的范围。因此，必须使用 java.math.BigInteger 类，它可以处理任意大小的整数。最后使用 .mod() 方法进行取模。
Python: Python 的 int 类型支持任意精度，不会溢出。因此，我们需要在计算总和后，手动对 2**64 进行取模操作。

代码

cpp
java
python

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    
    unordered_map<unsigned long long, unsigned long long> f_map;
    unsigned long long total_sum = 0;
    
    for (unsigned long long i = 1; i <= n; ++i) {
        unsigned long long x, y;
        cin >> x >> y;
        
        unsigned long long ans_i = 0;
        if (f_map.count(x)) {
            ans_i = f_map[x];
        }
        
        total_sum += i * ans_i;
        
        f_map[x] = y;
    }
    
    cout << total_sum << endl;
    
    return 0;
}

import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        Map<BigInteger, BigInteger> fMap = new HashMap<>();
        BigInteger totalSum = BigInteger.ZERO;
        
        for (int i = 1; i <= n; i++) {
            BigInteger x = sc.nextBigInteger();
            BigInteger y = sc.nextBigInteger();
            
            BigInteger ansI = fMap.getOrDefault(x, BigInteger.ZERO);
            
            BigInteger iBig = BigInteger.valueOf(i);
            totalSum = totalSum.add(iBig.multiply(ansI));
            
            fMap.put(x, y);
        }
        
        BigInteger modVal = BigInteger.valueOf(2).pow(64);
        System.out.println(totalSum.mod(modVal));
    }
}

n = int(input())
f_map = {}
total_sum = 0

for i in range(1, n + 1):
    x, y = map(int, input().split())
    
    ans_i = f_map.get(x, 0)
    
    total_sum += i * ans_i
    
    f_map[x] = y

# 对 2^64 取模，使用位运算 & (2^64 - 1) 效率更高且结果正确
print(total_sum & ((1 << 64) - 1))

算法及复杂度

算法: 哈希表
时间复杂度: $\mathcal{O}(N)$ 。每次操作都对应一次哈希表的查找和一次插入/更新，这些操作的平均时间复杂度都是 $\mathcal{O}(1)$ 。因此总时间复杂度与操作次数 N 成正比。
空间复杂度: $\mathcal{O}(U)$ ，其中 U 是在所有操作中遇到的不同 x 的数量。在最坏情况下，每次操作的 x 都不同，此时 U 等于 N，空间复杂度为 $\mathcal{O}(N)$ 。