10.19T3

Description

　　FJ给他的奶牛用二进制进行编号，每个编号恰好包含K个"1" (1<=K<=10)，且必须是1开头。FJ按升序编号，第一个编号的数是由K个连续的"1"组成。
　　请问第N(1<=N<=10^7)个编号是什么。

Input

　　输入仅一行为两个整数N和K。

Output

　　输出仅一行为一个二进制串，表示第N个二进制编号。

Sample Input

7 3

Sample Output

10110

Hint

【样例解释】符合条件的二进制数的前四个是：111 1011 1101 1110

肯定是跟组合数是有很大的关系

然后我们就可以从后往前面贪心就可以了

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int c[5000][20];
 5 int main(){
 6     int n,k;
 7     cin>>n>>k;
 8     if(k==1){
 9         cout<<1;
10         for(int i=1;i<n;i++)cout<<0;
11         return 0;
12     }
13     bool flag=false;
14     c[0][0]=1;
15     for(int i=1;i<=4500;i++){
16         c[i][0]=1;
17         for(int j=1;j<=15;j++){
18             c[i][j]=c[i-1][j]+c[i-1][j-1];
19         }
20     }
21     for(int i=4500;i;i--){
22         if(c[i-1][k]>=0&&c[i-1][k]<n)cout<<1,n-=c[i-1][k],flag=true,k--;
23         else if(flag)cout<<0;
24     }
25     return 0;
26 }

over