比特串

数位dp 组合数 usaco training 3.2 1382. 比特串 - AcWing题库 给定一个由若干个 $N$ 位 01 串构成的集合 $S$。

这个集合内的元素满足：

• 按照二进制表示从小到大排序。
• 每一个元素的 $N$ 位字符中，字符 $1$ 的数量均不超过 $L$。
• 所有满足上一条件的 $N$ 位 $01$ 串保证都在集合之中。

现在请你求出这个集合中的第 $I$ 个元素是多少。

输入格式

共一行，包含三个整数 $N,L,I$。

输出格式

输出集合中的第 $I$ 个元素。

数据范围

$1\le N\le 31$,
$1\le L\le N$,
$1\le I\le S$ 中元素的个数

输入样例：

5 3 19

输出样例：

10011

思路

直接考虑枚举答案, 既然要求第I个数, 只有当前位选1的方案数等于I时, 将当前位输出（即选0时方案数小于I）, 否则输出0, 这样可以贪心地求出最小。

设DP数组： f[i][j] 长度为i, 当前最多可以用j个1

先求出全排列数组, 之后预处理f数组。预处理时, j枚举应当超出i的限制, 最多为n, 因为状态定义的是最多可以用。第三层循环枚举当前选择的1个数k, 其大于i也没事, 全排列数组中对于这样的会初始化为0。

DP求解时从高到低位枚举, 若当前选0时方案数小于I, 说明当前需要选1, 即 f[i-1][L] < I 时, cout << 1, 然后再将 I-=f[i-1][L], 因为当前选1之后, 下一位能选的方案数就不能再是I了, 还要把当前能用的1个数减1, L--。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 32;
typedef long long LL;
LL f[N][N], c[N][N];
 
int main()
{
    LL n,l,m;
    cin >> n >> m >> l;
    
    c[0][0] = 1;
    for(int i = 1; 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];
    
    for(int i = 0; i <= n; i++) // 第i位
        for(int j = 0; j <= n; j++) // 当前位后面最多选j个1
            for(int k = 0; k <= j; k++) // 选1
                f[i][j] += c[i][k];
    
    for(int i = n; i >= 1; i--)
    {
        if(f[i-1][m] < l)
        {
            cout << 1;
            l -= f[i-1][m];
            m--;
        }else cout << 0;
        
    }
                
    
    return 0;
}