问题陈述
给你正整数 $N$ 和 $K$ 。
求所有不超过 $N$ 且满足以下条件的正整数 $x$ 的和，取模 $998244353$ ：
- $x$ 的 popcount 恰好是 $K$ 。
给你 $T$ 个测试用例，请逐个求解。
什么是 popcount？对于正整数 $y$ ， $\mathrm{popcount}(y)$ 表示二进制表示 $y$ 中的 $1$ 位数。例如， $\mathrm{popcount}(5)=2$ 、 $\mathrm{popcount}(16)=1$ 、 $\mathrm{popcount}(25)=3$ 。
从高到低遍历二进制位，如果当前位有1，则可以选择当前为0，设到当前选择的1的个数和为cur, 剩下的位在满足$C_{k-cur}^{i}$任意排列，
用dp $C_{i}^{j} = C_{i-1}^{j-1} + C_{i-1}{j}$ 求得排列C[N][N] 和 排列和P[N][N],
当前位为1的贡献是 高位1 * $C_{k-cur}^{i}$ + 右边所有排列情况的和P[i][k-cur]
我们求得的数量是严格小于给定数 $n$， 最后如果 $n$ 本身有k个1， 加上自身的贡献
注意取模优先级要比左移高 (1ull << (ull)(i-1))%mod)
#include <bits/stdc++.h>
#include <bit>
using namespace std;
using ull = unsigned long long;
// #define int ull
const ull mod = 998244353;
ull C[65][65], p[65][65];
void solve() {
ull n, k;
cin >> n >> k;
ull ans = 0;
for (int i = 59; i >= 0; i--) {
if ((1ull << (ull)i) > n) continue;
if (((1ull << (ull)i) & n) == 0) continue;
ull cur = __popcount(n >> (ull)(i+1));
if (cur > k) break;
ans += (C[i][k-cur] * (((n >> (ull)(i + 1)) << (ull)(i+1)) % mod)) % mod + p[i][k-cur];
ans %= mod;
}
if (__popcount(n) == k) {
ans = (ans + n) % mod;
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
C[0][0] = 1;
for (int i = 1; i <= 59; i++) {
C[i][0] = 1;
p[i][0] = 0;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
p[i][j] = (p[i-1][j] + p[i-1][j-1] + C[i-1][j-1] * (((1ull << (ull)(i-1))%mod))%mod) % mod;
}
}
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
扩展
康托展开
求 1∼N 的一个给定全排列在所有 1∼N 全排列中的排名。结果对 998244353 取模。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cout << #x << " " << x << endl
#define int ll
const int mod = 998244353;
const int N = 1e6 + 10;
int jie[N], a[N];
struct BIT {
int n;
vector<int> a;
BIT(int _n) : n(_n) {
a.assign(n+1,0);
}
void ad(int p) {
for (int i = p; i <= n; i += (i & -i)) {
a[i]++;
}
}
int pre(int p) {
int sum = 0;
for (int i = p; i >= 1; i -= (i & -i)) {
sum += a[i];
}
return sum;
}
};
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n+1);
for (int i = 1; i <= n; i++) cin >> a[i];
jie[0] = 1;
for (int i = 1; i <= n; i++) {
jie[i] = (i * jie[i-1]) % mod;
}
BIT tree(n);
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + ((a[i] - tree.pre(a[i]) - 1) * jie[n - i]) % mod) % mod;
tree.ad(a[i]);
}
cout << ans + 1;
return 0;
} /* 2025-06-12 15:12 */