2026-09-04
skip.rs
const A: u64 = 6364136223846793005;
const C: u64 = 1442695040888963407;
fn skip(state: u64, n: u64) -> u64 {
}
シードから始まる乱数生成器があり、1回進むたびに状態 s が「s * A + C を2の64乗で割った余り」に置き換わります。状態 state から n 回進めた後の状態を返す skip を書いてください。途中の状態から実行を再現するのに使うので、n が 10の12乗程度でもすぐに返る必要があります。n が 0 なら state をそのまま返します。
入力例 1
skip(0, 1)
出力例 1
1442695040888963407
入力例 2
skip(42, 0)
出力例 2
42
入力例 3
skip(42, 1_000_000_000_000)
出力例 3
1621903161643487274
Reference
fn skip(state: u64, n: u64) -> u64 {
let (mut s, mut mul, mut add) = (state, A, C);
for bit in 0..64 {
if (n >> bit) & 1 == 1 {
s = s.wrapping_mul(mul).wrapping_add(add);
}
add = add.wrapping_mul(mul).wrapping_add(add);
mul = mul.wrapping_mul(mul);
}
s
}
1回進める操作は、状態 s を s * A + C へ移す一次関数 f です。f を2回続けると f(f(s)) = (s * A + C) * A + C = s * A * A + (C * A + C) となり、これも「掛けて足す」形をしています。そこで、掛ける数 mul と足す数 add の組で「f を何回か続けた関数」を表します。ループの後半の2行がこの組を自分自身と合成する計算で、f を 2の bit 乗回続けた関数から、2の bit + 1 乗回続けた関数を作ります。新しい add は古い mul を使うので、mul より先に更新します。
n を2進数で見て、bit 番目が 1 のときだけ、その時点の組を s に適用します。適用する関数はどれも同じ f を何回か続けたものなので、順番を入れ替えても結果は変わらず、下のビットから順に適用してかまいません。n が 10の12乗でも、ループは64回で終わります。
2の64乗で割った余りを取る計算は、u64 の wrapping_mul と wrapping_add がそのまま行ってくれます。* と + で書くと、オーバーフローの検査が有効なビルド(デバッグビルドの既定)では、あふれた時点で panic します。
掲載したのは参考実装で、唯一の正解ではありません。n 回ループして1回ずつ進める実装でも結果は同じですが、n が 10の12乗だと、返るまでに長い時間がかかります。