CF1060H题解

qiuzx · 2023-01-02 16:36:10 · 个人记录

题意

一个大小为 5000 的数组，初始 a_1=x,a_2=y，其它全是 1。可以进行两种操作，将 a_i 的值修改为 a_j+a_k\bmod p，或将 a_i 的值修改为 a_j^d\bmod p。现在给定 d,p，保证 p 是质数。要求构造一个操作序列，并指定一个位置 t，使得无论初始的 x,y 值是什么，最终 a_t=xy\bmod p。2\le d\le 10,3\le p\le 10^9+9,d<p

思路

首先考虑简单情形。当 d=2,p=3 时，凑一凑我们可以发现，(x+y)^2-x^2-y^2=2xy，那么我们只需要能够实现减法和乘以常数即可。而减法可以看作是加上它 p-1 倍。乘以常数可以用龟速乘的方法，在 O(\log p) 的次数内实现乘以常数。

接下来我们考虑把 d\ne 2 的情况转化为 d=2 的情况。下一步我们的主要目标就是在 d\ne2 的时候实现 x\to x^2 的操作。注意到剩余的格子中放的是 1 而不是 0，所以我们肯定要利用这个 1 来构造。例如我们考虑 d=3，此时我们可以利用 (x+1)^3=x^3+3x^2+3x+1，减去对应的 x^3,x,1 即可。但这样的构造方式难以解决 d 更大的情况。不过我们不仅可以利用 (x+1)^d，还可以利用 (x+2)^d,\cdots,(x+k)^d。所以，一个自然的想法就是给每个 (x+k)^d 设一个系数 c_k，让 \displaystyle \sum_{i\ge 0}c_i(x+i)^d 的其它地方的系数都是 0，而 x^2 的系数是 1。这个可以通过高斯消元解决。这样我们就解决了这个问题，最终需要的总操作次数是 O(d\log p) 级别的，远低于要求的 5000。