题解：AT_abc406_e [ABC406E] Popcount Sum 3

· · 题解

同机房大家都写 dfs 就我不这么写。

纯计数。

我们先考虑 n 的 popcount 和 k 相等的情况。从高到低遍历 n 的每一位 1，假设当前是第 i 位（最低为第 0 位）。令我们枚举的数字的最高位到低 i+1 位都和 n 是一样的，并考虑第 i 位填 0 的情况，可以确定这样一定小于 n 并且不会重复。设 n 的第 0 位到第 i 位一共有 num 个 1，显然总共能产生 \binom{i}{num} 个不同的数字，在这些数字中考虑每个位的贡献。第 0 位到第 i-1 位的任意一位在这些数字中一共会在 \binom{i-1}{num-1} 个数字中为 1。所以第 0 位到第 i-1 位对答案产生的总贡献为 (2^{i}-1)\times \binom{i-1}{num-1}。至于高位的部分，将 n 的最高位到第 i+1 位取出，为 q，则这部分的贡献为 \binom{i}{num}\times q。注意到这种方法只能统计小于 n 的数字，所以最后输出的答案要加 n。

那么如果 n 的 popcount 不是 k 呢？如果 n 的 popcount 大于 k，那么就从低到高把 n 的 1 位置变成 0 直到 n 的 popcount 等于 k，然后直接按照上面的方法处理。如果 n 的 popcount 小于 k，也是从低到高遍历每一位，只不过是把 0 变成 1，并且答案不需要额外加 n。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 1000010
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define pii pair<int,int>
const ll mod = 998244353;
inline ll qpow(ll base,ll e){ll res=1;while(e){if(e&1)res=res*base%mod;base=base*base%mod;e>>=1;}return res;}
int t,k,cnt,num;ll n,ans,q;
ll f[N],g[N],p[N];
inline ll c(const int &x,const int &y){if(y > x)return 0;return f[x]*g[x-y]%mod*g[y]%mod;}

// 主函数
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> t;f[0] = p[0] = 1;
    for(int i = 1;i < N;++i)f[i]=f[i-1]*i%mod,p[i]=p[i-1]*2%mod;g[N-1] = qpow(f[N-1],mod-2);
    for(int i = N-2;i >= 0;--i)g[i]=g[i+1]*(i+1)%mod;
    while(t--){cin >> n >> k;ans = q = 0;num = 0;
        for(int i = 62;i >= 0;--i)if((n&(1ll<<i)))++num;
        if(num >= k){for(ll pos = 1;num != k;pos <<= 1)if(n & pos){--num,n&=(~pos);}ans = n;}// 把位置卸掉
        else for(ll pos = 1;num != k;pos <<= 1)if(!(n & pos)){++num,n|=pos;}// 补上
        for(int i = 62;i >= 0;--i){ll pos = (1ll<<i);if(!(n&pos))continue;
            ans = ans + c(i,num)*q%mod + (p[i]-1)*c(i-1,num-1)%mod;ans %= mod;--num;q += pos,q %= mod;
        }cout << ans << '\n';
    }
    return 0;
}