描述
考虑排好序的N(N<=31)位二进制数。
你会发现，这很有趣。因为他们是排列好的，而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。
你的任务是输出第i（1<=i<=长度为N的二进制数的个数）小的（注：题目这里表述不清，实际是，从最小的往大的数，数到第i个符合条件的，这个意思），长度为N，且1的位数的个数小于等于L的那个二进制数。
（例：100101中，N=6，含有位数为1的个数为3）。
格式
PROGRAM NAME: kimbits
INPUT FORMAT:
(file kimbits.in)
共一行，用空格分开的三个整数N，L，i。
OUTPUT FORMAT:
(file kimbits.out)
共一行，输出满足条件的第i小的二进制数。.
SAMPLE INPUT
5 3 19 SAMPLE OUTPUT 10011设长度为j的01串，1的个数不大于k的个数为f[j,k]
方程：f[j,k]=f[j-1,k]+f[j-1,k-1]; //分别表示在当前位加上0和加上1时的两种状况
边界：f[j,0]=1,f[0,j]=1;f[j,k](k>j)=f[j,j]
这样我们得到了所有的f[j,k](j,k∈Z, j,k>0),需要做的就是据此构造出所求字符串.
设所求串为S,假设S的位中最高位的1在自右向左第K+1位，那么必然满足F[K,L]< I,F[K+1,L] >=I,这样的K是唯一的。所以S的第一个1在从右至左第K+1位.因为有F[K,L]个串第K+1位上为0，所以所求的第I个数的后K位就应该是满足"位数为K且串中1不超过L-1个"这个条件的第I-F[K,L]个数。
于是我们得到这样的算法:
for K:=n-1 downto 0 do {题目保证有解，所以f[N,L]>I} if F[K,L]<I then begin s[N-K]:='1'; dec(I,F[K,L]);{第K+1位是1，所以I减去第K+1位是0的串的个数} dec(L); end; //注意I可能为2147483648th element ,所以用无符号整形存储I。F在F[32][32]为2147483648。所以F要用int64。
/* ID: tangr203 LANG: C++ TASK: kimbits */ #include<string.h> #include<stdlib.h> #include<stdio.h> double dp[33][33]; //设长度为j的01串，1的个数不大于k的个数为f[j,k] void init() { int i,j; for(i=0;i<33;i++) dp[0][i]=dp[i][0]=1; for(i=1;i<33;i++) for(j=1;j<33;j++) dp[i][j]=dp[i-1][j]+dp[i-1][j-1] ; } void work(int L,int N,double K) { if(L==0) return ; // printf("/n%d %d %.0lf %.0lf/n",L,N,K,dp[L-1][N]); if( dp[L-1][N]<=K ) { printf("1"); work(L-1,N-1,K-dp[L-1][N]); } else { printf("0"); work(L-1,N,K); } } int main() { freopen("kimbits.in","r",stdin); freopen("kimbits.out","w",stdout); init(); int L,N; double K; scanf("%d %d %lf",&L,&N,&K); work(L,N,K-1); printf("/n"); //system("pause"); }
