解法:数位 DP
时间复杂度:$O(n^3)$
这个题前几遍都听懵了,后来大睡了一觉再听一遍时,竟然慢慢就听懂了。
数位 $dp$,针对 $N$ 位就应该按位枚举,而按位枚举的策略又是什么呢?,接下来敲重点了。
_ _ _ _ _ _ _ _ _ _ N位
第一位填 $0$ 还是填 $1$ 是取决于后 $N - 1$ 位的组合方案数 $x$ 与 $k$ 的相比较而得到的。
当 $x \ge k$ 时, 就说明在剩下的 $N - 1$ 的组合方案中是包含第 $k$ 个元素的,则第一位就应该填 $0$。
当 $x < k$ 时, 就说明在剩下的 $N - 1$ 的组合方案中是不包含第 $k$ 个元素的,则第一位就应该填 $1$,因为侧面证明只包含在第一位为 $1$ 的集合中,由此第一位只能为 $1$,再看第二位时,应该在第一位的基础上进行比较,则 $ k -= x$,剩下的 $N - 2$ 位才能进行比较。
组合数的求解:$C_{b}^{a} = C_{b - 1}^{a} + C_{b - 1}^{a - 1}$
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 31;
int n, L, I;
int c[N][N], f[N][N];
int main()
{
cin >> n >> L >> I;
// 预处理出来组合数
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= i; ++j) {
if (!j) c[i][j] = 1;
else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
// 求解 f[][]
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k <= j; ++k) {
f[i][j] += c[i][k];
}
}
}
for (int i = 1, s = 0; i <= n; ++i) {
int x = f[n - i][L - s];
if (I > x) {
cout << 1;
I -= x;
++s;
}
else cout << 0;
}
}