AGC047E Product Simulation 题解

先不管 $A=B=0$ 的情况，构造 $A_3=1$ 只需要做比较 $1=[0<A_0+A_1]$ 然后自己加自己就可以构造出 $2$ 的幂次。然后拆二进制位，从高位到低位考虑 $A$ 并维护已经确定的高位和 $s$ 则第 $i$ 位的值可以被表示为 $b_i=[s+2^i<A+1]$ 然后顺便维护 $s$ 即可。

对每个二进制位分别考虑，设当前位的两个值为 $x,y\in\lbrace0,1\rbrace$ 则 $xy=[1<x+y]$ 直接做一下比较即可，最后考虑合并二进制位信息，模拟高精度乘法可得 $AB=\sum\limits_{i,j}(A_i\land B_j)2^{i+j}$ ，得到 $A_i\land B_j$ 的值之后直接自己和自己加 $i+j$ 次即可。看着用的结点数量和步数都特别多但是限制条件太松了怎么写都能过（我的实现用了 $29943$ 次操作）。~~我也不知道这个为啥是银牌题。~~

写的时候可能需要逻辑清晰一些，建议给操作稍微封装一下。

namespace lowspeed_song {

mt19937_64 mt(time(0));

inline void init() {
}

int idx = 3;

inline int newnode() { return idx++; }

vector<tuple<char, int, int, int>> ops;

inline void add(int x, int y, int z) { ops.emplace_back('+', x, y, z); }
inline void leq(int x, int y, int z) { ops.emplace_back('<', x, y, z); }

int pwr[30], bit[2][30], O;

inline void getbit(int val, int b[30]) {
    int lim = newnode(), s = newnode(), _ = newnode();
    add(val, O, lim); for (int i = 29; ~i; --i) {
        int val = newnode(); b[i] = newnode();
        add(s, pwr[i], val), leq(val, lim, b[i]), add(b[i], 2, _);
        for (int j = 0; j < i; ++j) add(_, _, _);
        add(s, _, s);
    }
}

inline void mul() {
    int t = newnode();
    for (int i = 0; i < 30; ++i) for (int j = 0; j < 30; ++j) {
        add(bit[0][i], bit[1][j], t), leq(O, t, t);
        for (int k = 0; k < i + j; ++k) add(t, t, t);
        add(2, t, 2);
    }
}

inline void sol([[maybe_unused]]int __testcase_id, [[maybe_unused]]int __testcase_sum) {
    int _ = newnode(); O = newnode();
    add(0, 1, _), leq(2, _, O), pwr[0] = O;
    for (int i = 1; i < 30; ++i) pwr[i] = newnode(), add(pwr[i - 1], pwr[i - 1], pwr[i]);
    getbit(0, bit[0]), getbit(1, bit[1]), mul();
    cout << ops.size() << '\n';
    for (auto &[x, y, z, w] : ops) cout << x << ' ' << y << ' ' << z << ' ' << w << '\n';
}

} // namespace lowspeed_song

隐藏／恢复文章

随机文章