Stringsobits
Kim Schrijvers
Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.
This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.
Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.
PROGRAM NAME: kimbits
INPUT FORMAT
A single line with three space separated integers: N, L, and I.
SAMPLE INPUT (file kimbits.in)
5 3 19
OUTPUT FORMAT
A single line containing the integer that represents the Ith element from the order set, as described.
SAMPLE OUTPUT (file kimbits.out)
10011
———————————————————————————————————————————————
把组合数求出来处理成前缀和
我们发现当I大于一段k长所有情况总和时，那么k+1位一定是1
那么这道题就做完了
其实最坑的一点，sizeof（S）=2147483648
…………………………
/*
ID: ivorysi
PROG: kimbits
LANG: C++
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
#define inf 0x7fffffff
#define MAXN 400005
#define ivorysi
#define mo 97797977
#define ha 974711
#define ba 47
#define fi first
#define se second
//#define pis pair<int,string>
using namespace std;
typedef long long ll;
int c[][];
int n,l;
ll k;
int num[];
void solve() {
scanf("%d%d%lld",&n,&l,&k);
siji(i,,n) c[i][]=;
siji(i,,n) {
int z=min(l,i);
siji(j,,z) {
c[i][j]=c[i-][j-]+c[i-][j];
}
}
siji(i,,n) siji(j,,l) {
c[i][j]+=c[i][j-];
}
int cnt=l;
gongzi(i,n-,) {
if(c[i][cnt]<k) {k=k-c[i][cnt];num[i+]=;--cnt;}
}
gongzi(i,n,) {
printf("%c",num[i]+'');
}
puts("");
}
int main(int argc, char const *argv[])
{
#ifdef ivorysi
freopen("kimbits.in","r",stdin);
freopen("kimbits.out","w",stdout);
#else
freopen("f1.in","r",stdin);
#endif
solve();
}