XOR Combination

2 secs 1024 MB

shinnshinn

問題

提出

テストケース

解説

上のビットから求めて行きます。桁DPを行います。

dp[iビット目][xがa未満確定か][yがb未満確定か] のようなdp配列を作成します。

$X$ の $i$ ビット目を固定した時、 $Y$ の $i$ ビット目も一意に定まります。

$0,1$ どちらも試し、 $A$ の $i$ ビット目が $1$ かつ、試したビットが $0$ の時に $X$ が $A$ 未満が確定します。 $Y$ も同様です。

最後のビットまで見た時、 $dp[0][0][0] + dp[0][0][1] + dp[0][1][0] + dp[0][1][1]$ が答えとなります。

実装ではdpのiビット目の部分は省いています。

実装

xxxxxxxxxx
 
use proconio::*;
​
fn solve() -> u64 {
    input! {
        a: u64,
        b: u64,
        c: u64
    }
​
    let mut dp = vec![vec![0; 2]; 2];
    dp[0][0] = 1;
    for d in (0..60).rev() {
        let mut ndp = vec![vec![0; 2]; 2];
        for da in 0..=1 {
            let db = (c>>d & 1) ^ da;
​
            // 0 -> 0 もしくは 0 -> 1の遷移が可能かどうか
            let ok_a = a>>d&1 >= da;
            let ok_b = b>>d&1 >= db;
            // 可能な場合 0, 1 のどちらになるか
            let na = if da < (a>>d&1) { 1 } else { 0 };
            let nb = if db < (b>>d&1) { 1 } else { 0 };
            if ok_a {
                ndp[na][1] += dp[0][1];
            }
            if ok_b {
                ndp[1][nb] += dp[1][0];
            }
            if ok_a && ok_b {
                ndp[na][nb] += dp[0][0];
            }
            ndp[1][1] += dp[1][1];
        }
        dp = ndp;
    }
​
    dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]
}
​
#[fastout]
fn main() {
    input! {
        t: usize,
    }
​
    for _ in 0..t {
        println!("{}", solve());
    }
}