[ARC222F] Triple Transformation

Genius_Star · 2026-09-11 18:48:33 · 题解

或许更好的阅读体验。

不是题。

思路：

因为你发现每次操作是唯一变换的，判定一个点能不能到另外一个点容易先想到能不能倍增第一个点找一下性质，即快速求出一个点变换 k 次后的点。

首先你发现操作特别抽象，考虑找一下性质；有一个比较显然的性质就是，每次操作的和是不变的，都是 x + y + z，于是 check 时如果和不同就可以直接 -1；先令 S = x + y + z。

更深层的，感觉每次变化的值没啥特别，具体的，例如第一个元素，只能变化成 x - y - z, 2x, y + z - x，可以先发现 x - y - z 和 y + z - x 是相反数，同时 (x - y - z) + S = 2x, (y + z - x) - S = -2x。

于是考虑模 S 意义下：

前面三种操作在模 S 意义下会变成 (2x, 2y, 2z)。
而最后一种操作会直接变成 (-2x, -2y, -2z)。

于是 (x, y, z) 变换 k 次后，设 a \equiv 2^k x, b \equiv 2^k y, c \equiv 2^k z，显然根据进行最后一次操作的奇偶性区分正负，有：

F_k(x, y, z) \equiv \begin{cases} (a, b, c) \\ (S - a, S - b, S - c)\end{cases}

那么具体是哪个呢？（赛时做到这里可以直接猜最后只要是这两个之一就一定有解就可以迅速做完）

再分析下性质，对于上面的操作：

如果变成 (2x, 2y, 2z)，显然三个数模 S 后和还是 S（因为只会将一个数减少另外两个数加的，而另外两个数加了后还是 <S）。
而如果变成 (-2x, -2y, -2z)，说明 x, y, z < \frac{S}{2}，于是误判到 (2x, 2y, 2z) 后是不取模的，三个数的和是 2S。

所以在每一步 F_{k - 1}(x, y, z) \to F_k(x, y, z) 时，我先全部乘以 2，如果模了之后和是 S，说明这步走的是 (2x, 2y, 2z)，否则走的是 (-2x, -2y, -2z) 的这步。

这样还是不好快速算走 k 步后的结果，考虑因为两次 -2 操作会互相抵消，只需要考虑 -2 出现了奇数次且最后一次 -2 的位置，因为这是最后一次 -2，所以后面一直 +2 不会出现三个数都 < \frac{S}{2} 的情况；而如果在最后那里出现了误判，直接 +2 的话，三个数和会先是 2S，我们论证它后面会一直是 2S：

具体的，设最后一次 -2 前是 (x, y, z)，后面是 (-2^k x, -2^k y, -2^k z) 它们不会出现三个数都 < \frac{S}{2} 的情况，所以误判后 (2^k x, 2^k y, 2^k z) 不会出现三个数都 > \frac{S}{2} 的情况。
而因为和是 2S，所以至少要两个 > \frac{S}{2} 的数，根据上面的限制；所以后面 (2^k x, 2^k y, 2^k z) 是恰好有两个 > \frac{S}{2} 的数，于是 2S \cdot 2 - 2S = 2S，和还是 2S 不变，一直往后推可以归纳证明得到。

于是算 F_k(x, y, z)，只需要考虑 (2^k x, 2^k y, 2^k z) 的和是 S 还是 2S 就行了；但是你会发现一个致命问题，即如果过程中出现了 0，前面的结论就会出现错误，你无法判定是 0 还是 S 等……

考虑尽量避免这种情况 2^k x \equiv 0 \pmod S，而 (x, S) 可能 >1，这样 x 的解特别多，不太好做，考虑：

如果 S 是偶数，那么经过一次操作后一定会全部变成偶数；
而如果全部都是偶数，显然可以全部除以二处理是不影响的。

于是暴力做最多 O(\log S) 次操作 S 就是奇数了，中间如果已经变化成功了就退出即可；此时 2^k x \equiv 0 \pmod S 因为 (x, S) = 1，所以只有 S \mid x，而根据 x 的范围，x 只能是 0，于是在变化过程中不会出现变成 0 的情况。

所以只有初始是 0 的情况：

如果只有一个 0，且 S 是奇数，所以其它两个一定有一个大的，所以每次操作是全部 +2 形的，前面的结论依旧适用。
如果有两个 0，显然操作后和本身相同，于是特判一下即可。
三个 0，一样特判。

特判后，只需要解决判定 F^k(x, y, z) 是否能到 (X, Y, Z) 的问题了，而 F^k(x, y, z) 是 2^k (x, y, z) 相关，于是本质是在解：

\begin{cases} 2^k x \equiv X \\ 2^k y \equiv Y \\ 2^k z \equiv Z\end{cases} \text{或} \begin{cases} 2^k x \equiv S - X \\ 2^k y \equiv S - Y \\ 2^k z \equiv S - Z\end{cases}

这两个方程组，只要其中一个有解，那么就有解。

这不就是 BSGS 吗，先设定一个 B，设 k = uB + v，于是方程转化为：

\begin{cases} 2^{uB} x \equiv 2^{-v}X \\ 2^{uB} y \equiv 2^{-v}Y \\ 2^{uB} z \equiv 2^{-v}Z\end{cases}

于是预处理所有的 (2^{-v}X, 2^{-v}Y, 2^{-v}Z)，枚举 u 的时候判定是否存在即可；显然 2^k 最多有 O(S) 种取值，令 B = \sqrt S 即可。

时间复杂度为 O(T \sqrt S \log S)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
struct Node{
    int x, y, z;
    inline bool operator<(const Node&rhs)const{
        if(x ^ rhs.x)
          return x < rhs.x;
        if(y < rhs.y)
          return y < rhs.y;
        return z < rhs.z;
    }
    inline bool operator==(const Node&rhs)const{
        return x == rhs.x && y == rhs.y && z == rhs.z;
    }
};
map<array<int, 3>, int> mp;
inline int qpow(int a, int b, int mod){
    int ans = 1;
    while(b){
        if(b & 1)
          ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int T, S, a1, a2, a3, b1, b2, b3, B;
inline void getnext(int &x, int &y, int &z){
    int tx = 0, ty = 0, tz = 0;
    if(y + z < x)
      tx = x - y - z, ty = 2 * y, tz = 2 * z;
    else if(x + z < y)
      tx = 2 * x, ty = y - x - z, tz = 2 * z;
    else if(x + y < z)
      tx = 2 * x, ty = 2 * y, tz = z - x - y;
    else
      tx = y + z - x, ty = x + z - y, tz = x + y - z;
    x = tx, y = ty, z = tz;
}
inline int solve(int X, int Y, int Z){
    if(X == S || Y == S || Z == S)
      return 2e9;
    int inv2 = (S + 1) >> 1;
    int mn = 2e9, id = -1;
    for(int i = 0; i < B; ++i){
        if(mp.count({X, Y, Z})){
            int w = mp[{X, Y, Z}];
            if(w < mn){
                mn = w;
                id = i;
            }
        }
        // cerr << X << ' ' << Y << ' ' << Z << ' ' << mn << ' ' << id << '\n';
        X = 1ll * X * inv2 % S, Y = 1ll * Y * inv2 % S, Z = 1ll * Z * inv2 % S;
    }
    if(id == -1)
      return 2e9;
    return mn * B + id;
}
inline void solve(){
    a1 = read(), a2 = read(), a3 = read(), b1 = read(), b2 = read(), b3 = read();
    S = (a1 + a2 + a3);
    if(b1 + b2 + b3 != S){
        puts("-1");
        return ;
    }
    if(a1 == b1 && a2 == b2 && a3 == b3){
        puts("0");
        return ;
    }
    if((!a1) + (!a2) + (!a3) == 2){
        puts("-1");
        return ;
    }
    int ans = 0;
    while((S & 1) ^ 1){
        ++ans;
        getnext(a1, a2, a3);
        // cerr << a1 << ' ' << a2 << ' ' << a3 << '\n';
        if(a1 == b1 && a2 == b2 && a3 == b3){
            write(ans);
            putchar('\n');
            return ;
        }
        if((b1 & 1) || (b2 & 1) || (b3 & 1)){
            puts("-1");
            return ;
        }
        a1 >>= 1, a2 >>= 1, a3 >>= 1, b1 >>= 1, b2 >>= 1, b3 >>= 1;
        S >>= 1;
    }
    B = sqrt(S);
    mp.clear();
    int base = qpow(2, B, S);
    for(int u = 0; u * B <= S; ++u){
        if(!mp.count({a1, a2, a3})){
            mp[{a1, a2, a3}] = u;
            // cerr << "Yes\n";
        }
        // cerr << "ins: " << a1 << ' ' << a2 << ' ' << a3 << ' ' << mp[{a1, a2, a3}] << '\n';
        a1 = 1ll * a1 * base % S, a2 = 1ll * a2 * base % S, a3 = 1ll * a3 * base % S;
    }
    // cerr << "B:" << b1 << ' ' << b2 << ' ' << b3 << '\n';
    ans += min(solve(b1, b2, b3), solve(S - b1, S - b2, S - b3));
    if(ans > 1e9){
        puts("-1");
        return ;
    }
    write(ans);
    putchar('\n');
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}