Sum Equals Xor の解説

古き良き桁dp。

dp[i][j] := 上からi桁目まで見た時にすでにL未満かのフラグがjの時の場合の数

としてdpすれば良い。

fn main() {
    input! {
        l: Chars
    }
    let l = l
        .iter()
        .map(|&e| if e == '1' { 1 } else { 0 })
        .collect_vec();

    let mut dp = vec![ModInt1000000007::new(0); 2];
    dp[1] += 1usize;
    for &num in l.iter() {
        let mut ep = vec![ModInt1000000007::new(0); 2];
        for j in 0..2 {
            let now = dp[j];
            if num == 1 {
                ep[j] += now * 2;
                ep[0] += now;
            } else {
                ep[j] += now;
                ep[0] += if j == 1 {
                    ModInt1000000007::new(0)
                } else {
                    now * 2
                };
            }
        }
        swap(&mut dp, &mut ep);
    }
    println!("{}", dp[0] + dp[1]);
}