描述 Description
作为一个神秘的电脑高手，Farmer John 用二进制数字标识他的奶牛。
然而，他有点迷信，标识奶牛用的二进制数字，必须只含有 K 位“1” (1 <= K <= 10)。 当然，每个标识数字的首位必须为“1”。
FJ 按递增的顺序，安排标识数字，开始是最小可行的标识数字（由 “1” 组成的一个 K 位数）。
不幸的是，他没有记录下标识数字。请帮他计算，第 N 个标识数字 (1 <= N <= 10^7)。
输入格式 InputFormat
第 1 行：空格隔开的两个整数，N 和 K。
输出格式 OutputFormat
如题，第 N 个标识数字。
样例输入 SampleInput
9876 7
样例输出 SampleOutput
1100011100001001
代码 Code
用 a[i][j]表示 i 位放 j 个 1 的方案数，可以发现这是个杨辉三角。。so 一步步逼近答案即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
int i,j,t,n,m,l,r,k,z,y,x;
int a[500005][11];
char ch[100005];
void find(int s)
{
int i,j,t;
if (s==0 || m==0) return ;
t=a[s+1][m+1]-a[s][m];
if (t>=n)
{
ch[s]='0';
find(s-1);
}
else
{
ch[s]='1';
m--;
n-=t;
find(s-1);
}
}
int main()
{
freopen("cowids.in","r",stdin);
freopen("cowids.out","w",stdout);
scanf("%d%d",&n,&m);
if (m==1)
{
printf("1");
for (i=1;i<n;i++) printf("0");
printf("\n");
return 0;
}
t=0;
a[1][1]=1;
for (i=0;i<=100000;i++) ch[i]='0';
for (i=2;a[i][m]<n;i++)
{
for (j=1;j<=m;j++) a[i][j]=a[i-1][j-1]+a[i-1][j];
}
t=m;
while (n-a[t][m]>0) n-=a[t][m],t++;
ch[t]='1';m--;
find(t-1);
while (t) printf("%d",(int)(ch[t]-'0')),t--;
printf("\n");
return 0;
}