月度归档:2018年10月

[Codeforces Round #513] H. Sophisticated Device

题目描述

定义一种机器,一共有5000个寄存器,前两个寄存器初始值分别为a, b,其他寄存器初始值均为1。该机器支持两种操作:

  1. ADD %dest, %src1, %src2:R[dest] = R[src1] + R[src2]
  2. POW %d, %s:R[dest] = pow(R[src], d)

所有操作均模p。要求用不超过5000条指令计算a*b。

题解

首先有加法我们就可以用类似快速幂的方式实现乘一个常数。这样,我们就可以构造出常数0(只需要乘p即可),实现减法(乘p-1获得相反数),除以一个常数(乘上它的逆元)。

精彩的是,我们可以用上述两条指令计算一个数的平方。考虑\(x^d, (x+1)^d, \cdots, (x+d)^d\)的二项展开,每一个都可以表示成\(1, x, x^2, \cdots, x^d\)的线性组合。这样,通过矩阵求逆就可以用\(x^d, (x+1)^d, \cdots, (x+d)^d\)表示出\(x^2\),从而完成了平方的计算。

有了平方操作,就可以用\(xy = ((x+y)^2-x^2-y^2)/2\)计算出两数之积了。