結果

問題 No.737 PopCount
ユーザー phsplsphspls
提出日時 2023-05-04 21:56:48
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1 ms / 1,000 ms
コード長 2,125 bytes
コンパイル時間 13,242 ms
コンパイル使用メモリ 377,696 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-22 11:50:25
合計ジャッジ時間 12,829 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 1 ms
5,248 KB
testcase_16 AC 1 ms
5,248 KB
testcase_17 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

const MOD: usize = 1e9 as usize + 7;

fn power(base: usize, times: usize) -> usize {
    if times == 0 { return 1usize; }
    if times == 1 { return base; }
    let temp = power(base, times/2);
    temp * temp % MOD * power(base, times%2) % MOD
}

fn main() {
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).ok();
    let n: usize = n.trim().parse().unwrap();

    let div2 = power(2, MOD-2);
    let limit = format!("{:b}", n).len();
    let mut result = 0usize;
    for i in 0..limit {
        let cnt = if i + 1 == limit { (n+1) - (1usize << i) } else { (n & ((n >> (i+1)) << (i+1))) / 2 + if ((n >> i) & 1) == 1 { 1 + n % (1 << i) } else { 0 } };
        let cnt2 = cnt / (1usize << i);
        // let cnt22 = cnt / (1usize << i) + if cnt % (1usize << i) > 0 { 1 } else { 0 };
        let span = (1usize << i) % MOD * ((1usize << (i+1)) % MOD) % MOD;
        result += if cnt2 == 0 { 0 } else { (cnt2 % MOD) * ((cnt2-1) % MOD) % MOD * div2 % MOD * span % MOD };
        // result += (cnt22 % MOD) * ((cnt22-1) % MOD) % MOD * div2 % MOD * span % MOD;
// eprintln!("{} {} {} {} {}", i, cnt, cnt2, span, result);
        result += (cnt2 % MOD) * (1usize << i) % MOD * (((1usize << i) * 3 - 1) % MOD) % MOD * div2 % MOD;
        // result += cnt2 * (1usize << i) % MOD * (1usize << i) % MOD;
        // result += cnt2 % MOD * (1usize << i) % MOD * (((1usize << i)-1) % MOD) % MOD * div2 % MOD;
// eprintln!("{} {}", i, result);
        let rest = cnt - cnt2 * (1usize << i);
        if rest > 0 {
            let rest_start = (1usize << i) + cnt2 * (1usize << (i+1));
            result += rest % MOD * ((rest_start * 2 % MOD + rest - 1) % MOD) % MOD * div2 % MOD;
        }
        result %= MOD;
// eprintln!("{} {}", i, result);
    }
// eprintln!("===================");
// let mut tempsum = 0usize;
//     for i in 0..limit {
//         tempsum += (1..=n).filter(|&j| ((j >> i) & 1) == 1).sum::<usize>();
// eprintln!("pass: {} {} {} {}", i, (1..=n).filter(|&j| ((j >> i) & 1) == 1).count(), (1..=n).filter(|&j| ((j >> i) & 1) == 1).sum::<usize>(), tempsum);
//     }
    println!("{}", result);
}
0