题解 | 大整数哈希-Java

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

/**
 * 主类，处理题目要求的功能：
 * 1. 维护一个从x到f(x)的映射关系
 * 2. 处理n次操作，每次操作返回当前f(x)值并更新映射
 * 3. 计算所有操作的i×ans_i之和，并对2^64取模后输出
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取操作次数n
        int n = sc.nextInt();

        // 创建HashMap用于存储x到f(x)的映射关系
        // 键为x（BigInteger类型，支持大整数）
        // 值为f(x)（BigInteger类型，初始值都为0）
        Map<BigInteger, BigInteger> fMap = new HashMap<>();

        // 用于累加所有i×ans_i的总和，初始值为0
        BigInteger totalSum = BigInteger.ZERO;

        for (int i = 1; i <= n; i++) {
            // 读取当前操作的x值（作为映射的键）
            BigInteger x = sc.nextBigInteger();
            // 读取当前操作的y值（用于更新f(x)）
            BigInteger y = sc.nextBigInteger();

            // 获取当前f(x)的值：
            // 如果map中存在x，则返回对应的value；否则返回默认值0
            BigInteger ansI = fMap.getOrDefault(x, BigInteger.ZERO);

            // 将当前操作次数i转换为BigInteger类型，便于后续大数运算
            BigInteger iBig = BigInteger.valueOf(i);
            // 计算i×ans_i，并累加到总和中
            totalSum = totalSum.add(iBig.multiply(ansI));

            // 更新映射关系：将f(x)的值设置为y
            fMap.put(x, y);
        }

        // 计算模值：2的64次方
        BigInteger modVal = BigInteger.valueOf(2).pow(64);
        // 对总和取模后输出结果
        System.out.println(totalSum.mod(modVal));
    }
}