4176: Masked Popcount

# Masked Popcount ### 内存 1024MB ### 时间 2S ## 题目描述 给定整数 $N$ 和 $M$，计算以下和的结果，对 998244353 取模: $\displaystyle \sum_{k=0}^{N} \rm{popcount}(k \mathbin{\&} M)$ 这里，$\mathbin{\&}$ 表示按位与运算，$\rm{popcount}(x)$ 表示 $x$ 的二进制表示中 1 的个数。 ## 输入格式 输入整数 $N$ 和 $M$。 ## 输出格式 输出一个整数，表示计算结果。 ## 输入输出样例 ### 输入样例1 ``` 4 3 ``` ### 输出样例1 ``` 4 ``` ### 输入样例2 ``` 0 0 ``` ### 输出样例2 ``` 0 ``` ### 输入样例3 ``` 1152921504606846975 1152921504606846975 ``` ### 输出样例3 ``` 499791890 ``` ## 数据范围与提示 【样例1说明】 - $\rm{popcount}(0\mathbin{\&}3) = 0$ - $\rm{popcount}(1\mathbin{\&}3) = 1$ - $\rm{popcount}(2\mathbin{\&}3) = 1$ - $\rm{popcount}(3\mathbin{\&}3) = 2$ - $\rm{popcount}(4\mathbin{\&}3) = 0$ 这些值的和是 4。 【样例2说明】 N = 0 或 M = 0 是可能的。 【数据范围】 $0 \le N,M < 2^{60}$ ## 题目来源 ABC356D