CF178C3 Smart Beaver and Resolving Collisions

ABBYY 的聪明海狸有很多爱好。其中之一就是构建高效的哈希表。哈希表中最严重的问题之一就是解决冲突。海狸对这个问题非常感兴趣，并决定深入研究。 我们假设哈希表由 $h$ 个单元格组成，编号从 $0$ 到 $h-1$。对象可以被添加到哈希表中，也可以从哈希表中删除。每个对象都有自己唯一的标识符。此外，每个对象还有一个对应的哈希值——一个在 $0$ 到 $h-1$ 之间的整数。当一个对象被添加到哈希表时，如果该对象的哈希值对应的单元格是空的，那么该对象就放在那里。如果该单元格已经被其他对象占用，就会发生冲突。当一个对象从哈希表中删除时，它所占用的单元格会变为空。 聪明的海狸最近学会了一种用线性探查法解决冲突的方法。具体如下。假设要添加的对象的哈希值为 $t$，而哈希表的第 $t$ 个单元格已经被占用。那么我们尝试将该对象添加到单元格 $(t+m)\bmod h$。如果这个单元格也被占用，则尝试单元格 $(t+2·m)\bmod h$，然后是 $(t+3·m)\bmod h$，以此类推。注意，在某些情况下，可能无法将新对象添加到哈希表中。保证本题输入数据不会出现这种情况。 操作 $a\bmod b$ 表示 $a$ 除以 $b$ 的余数。 这种方法立刻让海狸觉得非常低效，于是他决定评估其低效程度。现在给定一系列操作，每个操作要么是向哈希表中添加一个对象，要么是从哈希表中删除一个对象。当添加新对象时，会对哈希表进行一系列访问。访问已被占用的单元格称为“虚访问”。换句话说，如果上述算法最终将对象添加到单元格 $(t+i·m)\bmod h$（$i\geq 0$），那么恰好执行了 $i$ 次虚访问。 你的任务是计算给定操作序列中所有添加操作的虚访问总次数。当对象从哈希表中删除时，不进行虚访问。哈希表在所有操作开始前为空，即最初不包含任何对象。

输入的第一行包含三个整数 $h$、$m$ 和 $n$（$1\leq m

输出一个整数，表示哈希表所有添加操作的虚访问总次数。 请不要在 C++ 中使用 %lld 格式符来读写 64 位整数。建议使用 cin、cout 流和 %I64d 格式符。

由 ChatGPT 4.1 翻译