結果

問題 No.589 Counting Even
ユーザー bal4ubal4u
提出日時 2019-04-19 06:21:22
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,059 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 28,160 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 11:21:05
合計ジャッジ時間 1,247 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 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,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 1 ms
6,944 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 1 ms
6,944 KB
testcase_19 AC 1 ms
6,944 KB
testcase_20 AC 1 ms
6,940 KB
testcase_21 AC 1 ms
6,944 KB
testcase_22 AC 1 ms
6,944 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 1 ms
6,944 KB
testcase_26 AC 1 ms
6,944 KB
testcase_27 AC 1 ms
6,940 KB
testcase_28 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder: No.589 Counting Even
// 2019.4.19 bal4u
// 2項係数の奇偶性
//      1
//     1 1
//    1 2 1
//   1 3 3 1
//  1 4 6 4 1
//1 5 10 10 5 1  
// 上からn行目（0-indexed）の2項係数（n+1個）に現れる奇数の個数は
//     2 ^ bitcount64(n)
// 上からn行目（0-indexed）の2項係数（n+1個）に現れる偶数の個数は
//     n+1 - 2^bitcount64(n)

#include <stdio.h>

// ビット１の数（64ビット用）
int bitcount64(unsigned long long x)
{
	x = ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1) + (x & 0x5555555555555555ULL);
	x = ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2) + (x & 0x3333333333333333ULL);
	x = ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4) + (x & 0x0F0F0F0F0F0F0F0FULL);
	x = ((x & 0xFF00FF00FF00FF00ULL) >> 8) + (x & 0x00FF00FF00FF00FFULL);
	x = ((x & 0xFFFF0000FFFF0000ULL) >> 16) + (x & 0x0000FFFF0000FFFFULL);
	x = ((x & 0xFFFFFFFF00000000ULL) >> 32) + (x & 0x00000000FFFFFFFFULL);
	return (int)x;
}

int f[128];

int main()
{
	long long N;

	scanf("%lld", &N);
	printf("%lld\n", N+1-(1LL<<bitcount64(N)));
	return 0;
}
0