AtCoder ARC 135 A — Floor, Ceil Decomposition

問題: AtCoder ARC 135 A — Floor, Ceil Decomposition English · 한국어

正の整数xについて、x <= 4ならf(x) = xです。それ以外の場合、xをfloor(x / 2)とceil(x / 2)に分け、対応する関数値の積を998244353で割った余りとして定義します。

f(x) = f(floor(x / 2)) * f(ceil(x / 2)) mod 998244353。

分割後の2つの値はいずれも元の値より小さいため、再帰計算は最終的に基底条件に到達します。メモ化により同じ値の再計算を避けます。各再帰の深さで現れるのは元の数を繰り返し半分にした値の切り捨てまたは切り上げだけなので、深さごとの異なる状態は最大2つです。したがって状態数と再帰の深さはいずれもO(log x)で、メモ表の空間計算量もO(log x)です。

掛け算の前に各再帰結果を法で剰余にします。各因数は法より小さいため、その積は998244353²未満であり、Javaの符号付きlongに収まります。また、切り上げた半分はx / 2 + x % 2で計算するため、x + 1のオーバーフローも起こりません。

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    private static final long MOD = 998244353L;
    private static final Map<Long, Long> memo = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        long x = Long.parseLong(input.readLine().trim());
        System.out.println(value(x));
    }

    private static long value(long x) {
        if (x <= 4) {
            return x;
        }

        Long cached = memo.get(x);
        if (cached != null) {
            return cached;
        }

        long lower = x / 2;
        long upper = lower + x % 2;
        long result = value(lower) * value(upper) % MOD;
        memo.put(x, result);
        return result;
    }
}