ABC-356D题解

· · 题解

ABC-356D题解

注:借鉴官方题解

题意

给出 n,m 求 (\sum_{k=0}^{n}\operatorname{popcount}( k\& m) ) \bmod 998244353 。

其中 \operatorname{popcount}(x) 表示 x 的二进制中 1 的个数。

思路

显然可以发现，对于第 j 位，当 k 与 m 的第 j 位为 1 时，才会产生贡献。

于是，本题转化成了，对于每个满足 m 的第 j 位为 1 的 j，求出 [0,n] 中第 j 位为 1 的 k 的个数。

首先，[0,2^j-1] 中的数，它的第 j 位一定不为 1。

其次，[2^j,2^{j+1}) 中的数，它的第 j 位一定为 1 。

（可以写出二进制的形式加深理解）

因此，在 [0,2^{j+1}) 中，共有 2^j 个满足上述要求的数。

而对于一个数 i，它的第 j 位一定与 i+2^{j+1} 一致（因为只对 j+1 以及它左边的位有影响）。

因此，[2^{j+1},2\times2^{j+1}) 之间也有 2^j 个数满足要求，以此类推。

所以，对于非负整数 k，在 [0,k\times2^{j+1}) 之间的整数中，有 k\times 2^j 个数符合要求。

再来讨论剩下的不足 2^{j+1} 的部分。

设 l=n \bmod 2^{j+1}。

则如果 l \geq 2^j，则 k\times2^{j+1}+2^j 到 k\times 2^{j+1}+l 之间共 l-2^j+1 个数符合要求。

否则无贡献。

最后统计答案。

Code

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
const int p=998244353;
int n,m;
int ans;
int fun(int i,int n)
{
    int p2=(1ll<<i);
    int k=n/(2*p2);
    int res=k*p2;
    int l=n%(2*p2);
    if(l>=p2) res+=(l-p2+1);
    return res%p;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<60;i++)
    {
        if((1ll<<i)&m) 
        {
            ans+=fun(i,n);
            ans%=p;
        }
    }
    cout<<ans;
    return 0;
}