时间复杂度 $O(n^3)$
看了几遍不是很懂,给出自己的理解。
题目意思:
一共N位,1的个数不超过L的集合。从小到大排序第I的数是多少。
从最高位依次往下填写:
最高位填写1还是0是由后面的可以填的多少方案数与I比较决定的。
假设除去最高位,还剩x种方案可以填写。
如果$x >= I$ 说明 第I小的数在x种方案里面,应该填写0;
如果$x < I$ 说明 第I小的数不在x种方案里面,因为是从高到低填每一个数,所以应该填写1, I -= x;
f[a][b]
表示所有长度为a,1的个数不超过b的方案。
c[a][b]
表示排列组合,在a中选b个数。
f[a][b] = c[a][0] + c[a][1] + ....c[a][b]
C++ 代码
#include <iostream>
using namespace std;
const int N = 31;
typedef long long LL;
LL c[N][N], f[N][N];
LL n, L, I;
int main()
{
// 预处理31的所有排列组合
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];
cin >> n >> L >> I;
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++) // 这里f[i][j] 有具体含义, 如f[5][10] 表示一个5位,1的个数不超过10
for (int k = 0; k <= j; k ++)
f[i][j] += c[i][k];
for (int i = 1, s = 0; i <= n; i ++) // s 表示1的个数
{
LL x = f[n - i][L - s]; // 剩下n - i位, 1 的个数不超过 L - s
if (I > x)
{
cout << 1;
s ++;
I -= x;
}
else cout << 0;
}
return 0;
}