結果

問題 No.589 Counting Even
コンテスト
ユーザー bal4u
提出日時 2019-04-19 06:21:22
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 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