The 2023 ICPC Asia Shenyang Regional Contest F. Ursa Minor

The 2023 ICPC Asia Shenyang Regional Contest F. Ursa Minor

首先，\(B_s\cdots B_t\) 的 Tool 可以直接变成一个 \(k=\gcd (B_s,\cdots ,B_t)\) 的 Tool
但是这还不够，事实上因为环的同构，我们实际可以简化为一个 \(d=\gcd(n,k)\) 的 Tool
具体来说，可以把数组在环上 Shift 视作 \(\mathbb{R}[y] / (y^n - 1)\) 上的乘一个多项式。
\(A(y) = a_0 + a_1y + a_2y^2 + \dots + a_{n-1}y^{n-1}\) 乘上一个 \((y-1)\) 对应环的 Shift 。
操作 \(k\) 在 \(0\) 上则对应的是 \(P_k(y) = 1 + y + y^2 + \dots + y^{k-1}\)
接下来放一下 gemini 给的证明，非常关键的一个条件是操作可以加任意实数，如果限制了整数就不对了。

---

Because we can apply the tool at any starting position and with any weight, the set of all possible planet states we can generate is simply all possible polynomial multiples of \(P_k(y)\).

In abstract algebra, this set is called the ideal generated by \(P_k(y)\) modulo \(y^n - 1\). Let's denote this ideal as \(\langle P_k(y) \rangle\).

Our goal is to prove that the ideal generated by a \(k\)-tool is mathematically identical to the ideal generated by a \(d\)-tool. In other words, we want to prove:

\[\langle P_k(y) \rangle = \langle P_d(y) \rangle \]

where \(P_d(y) = 1 + y + \dots + y^{d-1}\) and \(d = \gcd(n, k)\).

---

In the ring of polynomials \(\mathbb{R}[y]\), the ideal generated by a polynomial modulo \(y^n - 1\) is exactly equivalent to the ideal generated by the greatest common divisor (GCD) of that polynomial and \(y^n - 1\).

Therefore, the "simplest" equivalent tool we can form is exactly:

\[g(y) = \gcd(P_k(y), y^n - 1) \]

Let's calculate this GCD. Notice that we can multiply our core polynomials by \((y-1)\) to get a simpler form:

\[P_k(y) \cdot (y - 1) = y^k - 1 \]

\[P_n(y) \cdot (y - 1) = y^n - 1 \]

This means \(P_k(y) = \frac{y^k - 1}{y - 1}\).

Now we substitute this into our GCD expression:

\[g(y) = \gcd\left(\frac{y^k - 1}{y - 1}, y^n - 1\right) \]

Because \(y-1\) is a common factor of both \(y^k - 1\) and \(y^n - 1\), we can pull the division by \((y-1)\) outside of the GCD operation:

\[g(y) = \frac{\gcd(y^k - 1, y^n - 1)}{y - 1} \]

It is a well-known property of polynomials that \(\gcd(y^k - 1, y^n - 1) = y^{\gcd(k, n)} - 1\). Since we defined \(d = \gcd(n, k)\), we have:

\[\gcd(y^k - 1, y^n - 1) = y^d - 1 \]

Substituting this back into our equation for \(g(y)\):

\[g(y) = \frac{y^d - 1}{y - 1} \]

If we expand this fraction back out, we get:

\[g(y) = 1 + y + y^2 + \dots + y^{d-1} = P_d(y) \]

---

这样我们的最小操作 \(d\) 就一定是 \(n\) 的因数，于是可以直接把数字按照下标模 \(d\) 分类。询问合法的充要条件是模 \(d\) 同余族的和相等。必要性显然，每次操作一定改变每个族种一个元素。充分性也很简单，直接把前 \(n-d\) 个变成对应的，最后操作对应差值即可。

于是问题变成两部分，一个是求静态区间 gcd，得到 \(d\)；另一个是询问序列 \(a_l,\cdots a_r\) 在下标 \(\mod d\) 剩余系下和是否相等（\(a\) 带单点修）。

对于 \(d\) 分治。如果 \(d\) 比较小和 \(d\) 比较大分别用不同的根号数据结构维护，均摊复杂度即可。