传送门
思路：递归&组合数学。
显然对于长度为 l e n len len的 01 01 01串，包含 k k k个1且第一位为 1 1 1的个数为从 l e n − 1 len-1 len−1中选出 k − 1 k-1 k−1个1.
即： C ( n − 1 , k − 1 ) C(n-1,k-1) C(n−1,k−1)个。
所以我们每次可以求出第一个1在那个长度里。然后先输出距离上一轮的第一个1之间由多少个0，再输出这轮的1，不断递归，到最后 k = 0 k=0 k=0，再输出剩下0的个数。(因为最后一个1后面再没有1，全部是0，即输出 w w w个0即可)。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int C(int n,int m){ int ans=1; for(int i=n-m+1;i<=n;i++) ans*=i; for(int i=1;i<=m;i++) ans/=i; return ans; } int main(){ int n,k; scanf("%d%d",&n,&k); int pre=k-1,w; for(;k;k--){ //递归每次的第一位的1. w=k-1; int x=C(w,k-1),sum=0; while(sum+x<n){ sum+=x; x=x*(++w)/(w-k+1); //不能写 x*=(++w)/(w-k+1) 它会先算右式(++w)/(w-k+1) } for(int i=1;i<=pre-w-1;i++) printf("0"); //此时的(w+1)表示当求第一个1到最后一位的长度. // 之前的剩下的长度为pre,距离上一个第一位1的个数为pre-(w+1),所以这之间的数要填0. n-=sum,pre=w;//这里pre=w,而不是=w+1,因为每次要填一个1,所以剩下的数还要减去1. printf("1"); } for(int i=1;i<=w;i++) printf("0"); return 0; }