题解：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

。

参考代码：

CPP

#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;
}

题解：AT_abc406_e [ABC406E] Popcount Sum 3

文章操作

相关推荐

评论

题解：AT_abc406_e [ABC406E] Popcount Sum 3