CF178C2 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 翻译