Universal Cup 4-19 M

準急が飛んだ(物理) + 1ヵ月ぐらい全くコードを書いてないことに気づいたので参加

無事Mが炎上。反省したらシンプルに書けたので投稿。そもそもADD DIV モノイド に帰着できますよね、というのは置いておいて…

オーバーフローに目をつぶればそのままsegtreeに乗る

struct S {
    Int len;
    Int v;
};

Int pow2(Int n) { return Int(1) << n; }

S op(S l, S r) {
    Int len = l.len + r.len;
    Int v = l.v + r.v * pow2(l.len);

    return {len, v};
}

オーバーフローを回避するためには、ある程度区間が長くなったら短い区間に帰着、という操作を入れればよい。

using Int = __int128;

struct S {
    Int len;
    Int v;
};

Int pow2(Int n) { return Int(1) << n; }

S op(S l, S r) {
    Int len = l.len + r.len;
    Int v = l.v + r.v * pow2(l.len);

    if (len > 40) {
        // 長さ40の区間に帰着する
        // v = div * 2^len + rem (0 <= rem < 2^len)として、
        // v'= div * 2^40  + rem'に変換する。
        Int div = floor_div(v, pow2(len));
        Int rem = v - div * pow2(len);

        if (rem < pow2(35)) {
            // remが小さい => そのまま
        } else if (rem > pow2(len) - pow2(35)) {
            // remが大きい => 繰り上がりとの距離を保持
            rem = rem - pow2(len) + pow2(40);
        } else {
            // その他 => 適当に真ん中に設定
            rem = pow2(39);
        }

        len = 40;
        v = rem + div * pow2(40);
    }

    return {len, v};
}