結果

問題 No.737 PopCount
ユーザー @abcde@abcde
提出日時 2019-04-20 09:21:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 5,361 bytes
コンパイル時間 1,389 ms
コンパイル使用メモリ 164,352 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-25 22:08:07
合計ジャッジ時間 2,469 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
const LL LIMIT = 61;
LL FAC[LIMIT + 1];
LL pow2[LIMIT + 1];
LL INV[LIMIT + 1];

// Use of dynamic bitset to convert decimal numbers.
// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers
// 10進数 → 2進数.
// @param n: 2進数へ変換したい10進数.
// @param d: 2進数表記する桁数.
// @return: 2進数.
string decimalToBinary(LL n, int d) {

    // 1. ゼロの場合.
    string ret = "";
    if(n == 0){
        while(ret.size() < d) ret = "0" + ret;
        return ret;
    }
    
    // 2. ゼロでない場合.
    LL ln = abs(n);
    do{
        ret = string((ln & 1) ? "1" : "0") + ret;
    }while((ln /= 2) > 0);
    while(ret.size() < d) ret = "0" + ret;
    
    // 3. 負数の場合.
    if(n < 0) ret = "-" + ret;
    return ret;

}

// Fermat's little theorem を 適用するため, 大きな冪乗の計算ができるようにする.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL inverse(LL a, LL b){
    LL t = 1;
    while(b) {
        if(b & 1) t = (t * a) % MOD;
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return t % MOD;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param P_: 対象となる要素の個数.
// @param Q_: 選択する要素の個数.
// @return:  組み合わせ(nCk)の計算結果.
LL comb(LL P_, LL Q_){
    if(P_ < 0 || Q_ < 0 || Q_ > P_) return 0;
    LL ret = FAC[P_] * INV[Q_] % MOD * INV[P_ - Q_] % MOD;
    return ret;
}

//  PopCount の 部分和 を 計算.
// @param b: 2進数に変換した整数.
// @param r: 計算済の桁数(※上位r桁).
// @param l: 計算予定の桁数(※下位l桁).
// @return: PopCount の 部分和 を 返却.
LL subPopCount(string b, int r, int l) {

    // 1. 1 の 個数.
    int lOne = 0;
    for(int i = 0; i < r; i++) if(b[i] == '1') lOne++;
    
    // 2. base の 計算.
    LL base = 0;
    for(int i = 0; i < r; i++) base += pow2[i + l] * (b[r - 1 - i] - '0'), base %= MOD;
    
    // 3. PopCount の 部分和 を 計算.
    // ex.
    // 1010XXX の パターンであれば, XXX部分 と 1010000部分 で 計算して, 合計.
    // 3-1. XXX部分 を 計算.
    LL lx = 0;
    for(int i = 1; i <= l; i++) lx += comb(l - 1, i - 1) * (i + lOne), lx %= MOD;
    lx *= (pow2[l] - 1);
    lx %= MOD;
    
    // 3-2. 1010000部分 を 計算.
    LL rx = 0;
    for(int i = 0; i <= l; i++) rx += comb(l, i) * (i + lOne), rx %= MOD;
    rx *= base;
    rx %= MOD;
    
    // 3-3. 結果を返却.
    LL res = lx + rx;
    res %= MOD;
    // cout << "r=" << r << " l=" << l << endl;
    // cout << "base=" << base << " lOne=" << lOne << " lx=" << lx << " rx=" << rx << " res=" << res << endl;
    return res;
}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    
    // 2. 準備事項.
    // 2-1. 階乗, 逆元を計算.
    FAC[0] = 1;
    for(int i = 1; i < LIMIT; i++) FAC[i] = i * FAC[i - 1] % MOD;
    for(int i = 0; i < LIMIT; i++) INV[i] = inverse(FAC[i], MOD - 2) % MOD;
    // for(int i = 0; i < LIMIT; i++) cout << "FAC[" << i << "]=" << FAC[i] << " INV[" << i << "]=" << INV[i] << endl;
    
    // 2-2. 2のべき乗計算.
    pow2[0] = 1;
    for(int i = 1; i < LIMIT; i++) pow2[i] = 2 * pow2[i - 1], pow2[i] %= MOD;
    // for(int i = 0; i < LIMIT; i++) cout << pow2[i] << endl;
    
    // 2-3. 2進数に変換.
    string binN = decimalToBinary(N, LIMIT);
    // cout << binN << endl;
    
    // 3. V(1) ～ V(N) の 合計 を 計算.
    // 1e18 は, 110111100000101101101011001110100111011001000000000000000000 (60桁)
    // なので, 61桁で調べることにする.
    // 
    // ex.
    // V(80) ～ V(87) までの和を計算.
    // 1010000 (80)  1010001 (81)  1010011 (83)  1010111 (87)
    //               1010010 (82)  1010101 (85)
    //               1010100 (84)  1010110 (86)
    // -> 1010XXX の パターンとみて, 
    //     XXX 部分 の 合計は, (2 の 3乗 - 1) * (2C0 * 3 + 2C1 * 4 + 2C2 * 5) = 7 * (3 + 8 + 5) = 112.
    // 1010000 部分 の 合計は, (2 の 6乗 + 2 の 4乗) * (3C0 * 2 + 3C1 * 3 + 3C2 * 4 + 3C3 * 5) = 80 * (2 + 9 + 12 + 5) 
    // = 2240.
    // -> 合計 2352 となるが, OK のはず.
    LL t1 = subPopCount("1010000", 4, 3);  // base=80 lOne=2 lx=112 rx=2240 res=2352
    LL t2 = subPopCount("01111", 1, 4);    // base=0  lOne=0 lx=300 rx=0    res=300
    LL t3 = subPopCount("10111", 2, 3);    // base=16 lOne=1 lx=84  rx=320  res=404
    // cout << t1 << " " << t2 << " " << t3 << endl;
    
    // 3-1. binN を 先頭(i = 0)から, 末尾の1つ手前(i = LIMIT - 2)まで, 順次見ていく.
    LL ans = 0;
    for(int i = 0; i < LIMIT - 1; i++){
        if(binN[i] == '1'){
            string tBin = binN;
            tBin[i] = '0';
            ans += subPopCount(tBin, i + 1, LIMIT - i - 1);
            ans %= MOD;
        }
    }
    
    // 3-2. binN の 末尾(i = LIMIT - 1)を確認.
    if(binN[LIMIT - 1] == '0') ans += subPopCount(binN, LIMIT, 0), ans %= MOD;
    if(binN[LIMIT - 1] == '1') ans += subPopCount(binN, LIMIT - 1, 1), ans %= MOD;
    
    // 4. 後処理.
    cout << ans << endl;
    return 0;
    
}
0