Even Numbers

题目大意

给定一个二元函数$calc(i, j)$

当$i=n$时，计算当$0 \leq m \leq n$时，$calc(n, m)$有多少个偶数

Time : 1000 ms
Memory: 262144 kB

解题思路及分析

对杨辉三角、组合数比较熟悉的可以一眼看出来给的公式就是杨辉三角也就是组合数
不熟悉的打一下表或者手算几行也能看出来，但是由于n最大为1e18所以不能直接算
对于组合数有一个结论：当$n \& m == m$时$C_n^m$为奇数，有了这个结论这道题直接就可以做了
另外不知道结论的也可以直接推规律，我就是直接硬推出来的，下面给出推的过程
首先第一步是对2取余打表，最开始是统计的偶数发现没什么规律，然后发现统计奇数更有规律性，每一行的奇数个数均为2的幂次
然后去寻找规律，最先发现的就是对于2的幂次的行奇数个数均为2（首尾的两个1），奇数行的奇数个数为前一行的二倍。此时还没发现什么规律，然后继续观察，发现对于6、48这些行均为4，而6=2+4，48=32+16，于是猜想和二进制有关系，打表把每行的二进制输出，发现关键信息：第i行的奇数个数等于$2^k$，其中k为i的二进制中1的个数。从偶数个数可以求出奇数个数，至此找到规律，即可顺利AC

AC代码

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

llong n;

int main() {
    #ifdef LOCAL
        freopen("in.in", "r", stdin);
        freopen("out.out", "w", stdout);
    #endif

    int T;	cin >> T;
    while (T--) {
        cin >> n;
        llong tmp = n, cnt = 1;
        while (tmp) {
            if (tmp & 1) {
                cnt <<= 1;
            }
            tmp >>= 1;
        }
        cout << n + 1 - cnt << endl;
    }
    return 0;
}