AcWing 1382. 比特串
原题链接
简单
作者:
qgc123
,
2021-11-23 21:45:13
,
所有人可见
,
阅读 344
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 35;
ll n, l, k, c[N][N], f[N][N];
int main(void){
scanf("%lld%lld%lld", &n, &l, &k);
// c[i][j] : 从长度为i的01串中选取出j个1不同取法的数量
for(int i = 0; i <= n; i++){
for(int j = 0; j <= i; j++){
if(!j) c[i][j] = 1; // c[i][0] = 1 从长度为i的01串中选0个1只有一种可能
else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
//对于c(i,j)有等于c(i-1,j)+c(i-1,j-1)
//即有从长度为i的01串中选取j个1的不同取法的数量等于从i-1个01串中选取j和j-1个1的数量的和
/*
如 3 2
100
010
001
110
101
011
111
*/
}
}
for(int i = 0; i <= n; i++){
// 此处 j 可以大于 i 因为 f[i][j] 代表长度为 i 时 1 的个数"不超过" j 个的方案数
for(int j = 0; j <= n; j++){
for(int k = 0; k <= j; k++){
// 长度为 i 时 1 的个数不超过 j 个的方案数 (所以 : k <= j)
f[i][j] += c[i][k];
}
}
}
// 判断第 i 位数字之前已经出现 j 个 1 (高位 -> 低位顺序)
for(int i = 1, j = 0; i <= n; i++){
// 1 的总个数不能超过 l (j <= l) : 剩余位 1 的个数不能超过 l - j
// x : 剩余低位中 1 的个数不超过 剩余 1 的个数(l - j) 的总方案数
// 如果 x < k(第 k 小) : 所求数不存在总长度为 n - i 的二进制数中(范围之外代表此数更大一些)
// 故此位必须为 1 否则矛盾
ll x = f[n - i][l - j];
if(k > x) {
putchar('1'); // 此位为 1
j++; // 出现的 1 的个数增加一个
k -= x; // (第 k 小) -> (第 k - x 小)
}
else putchar('0'); // 否则在范围内 : 此位为 0
}
return 0;
}