結果

問題 No.420 mod2漸化式
ユーザー @abcde@abcde
提出日時 2019-03-05 01:07:11
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,059 bytes
コンパイル時間 1,551 ms
コンパイル使用メモリ 159,348 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 14:06:34
合計ジャッジ時間 2,564 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 0 ms
6,944 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 2 ms
6,944 KB
testcase_30 AC 1 ms
6,940 KB
testcase_31 AC 1 ms
6,940 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 2 ms
6,944 KB
testcase_34 AC 1 ms
6,940 KB
testcase_35 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    LL X;
    cin >> X;
    
    // 2. f(n) = X となる n は？
    // ex. 
    // f(64) = f(32) = f(16) = f(8) = f(4) = f(2) = f(1) = 1
    // f(48) = f(24) = f(12) = f(6) = f(3) = f(1) + 1 = 2
    // f(112) = f(56) = f(28) = f(14) = f(7) = f(3) + 1 = 3
    // ...
    // -> n を 2進数表記したときの 1の個数と同じに見える.
    
    // 2-1. X > 31 の 場合.
    // n の 条件から, 31桁を超えるものは, 考えなくて良さそう.
    // -> X が 31を超えたら, n の個数, n の総和 は, 0 のはず.
    LL nTotal = 0, nCount = 0;

    // 2-2. X <= 31 の 場合.
    if(X <= 31){
        // X を 2進数表記した場合の 1 の個数(bitOne個)は？
        // -> 今回は, このロジックは使わない.
        // cout << X << endl;
        // int bitOne = 0;
        // while(X) bitOne += (X % 2 == 1), X /= 2;
        // cout << bitOne << endl;
        
        // n の 個数 nCount は？
        // -> 31桁を想定すると, 31 から X個を選択する組み合わせの数に等しいと考えられる.
        nCount++;
        // for(int i = 31; i > 31 - bitOne; i--) nCount *= i, nCount /= (32 - i);
        for(int i = 31; i > 31 - X; i--) nCount *= i, nCount /= (32 - i);
        
        // n の 合計 nTotal は？
        // -> 1111111111111111111111111111111 (31桁の2進数) を (X * nCount ÷ 31) 個分と理解.
        // -> 1111111111111111111111111111111 は, 10進数で, 2147483647 に注意.
        // nTotal = 2147483647 * X * nCount / 31;
        // -> system_test1.txt, test15.txt - test17.txt における Overflow対策.
        // nTotal = 2147483647 * X * (nCount / 31);
        // -> さらに, test31.txt 対策.
        if(nCount >= 31) nTotal = 2147483647 * X * (nCount / 31);
        else             nTotal = 2147483647 * X * nCount / 31;
    }
    
    // 3. 後処理.
    cout << nCount << " " << nTotal << endl;
    return 0;
    
}
0