奶牛编号(Cowids) [NOIP模拟]

问题描述
作为一个神秘的电脑高手,Farmer John 用二进制数字标识他的奶牛。然而,他有点迷信,标识奶牛用的二进制数字,必须只含有 K 位“1”(1 <= K <= 10)。当然,每个标识数字的首位必须为“1”。FJ 按递增的顺序,安排标识数字,开始是最小可行的标识数字(由“1”组成的一个 K 位数)。不幸的是,他没有记录下标识数字。请帮他计算,第 N 个标识数字(1 <= N <= 10^7)。

输入
第 1 行:空格隔开的两个整数,N 和 K。

输出
如题,第 N 个标识数字

输入输出样例
7 3

10110

思路

我思路真的很复杂（因为我太蒻了），不过有一些是很有价值的思想

就以样例做比方，其前几个排列是：

除了第一个，我们发现，把相同长度的分为一组，第i组内的大小为C(2+i,i)　　[扩展到整道题就是C( k-1+i , i )]

我们就可以通过组合数的方式快速找到第n个数属于第几组

而在某一组内如何快速找到它的位置呢？

我们就数据中长度为5的那一组分析，抛开开头的1，0的位置依次为

1 2　　1 3　　1 4　　2 3　　2 4　　3 4

也就是求C(2+i,i)中字典序大小的第m项 (设第n个数在这一组排第m项)

显然一项一项枚举是会T掉的，那我们可以怎样判断出某一位是几？

我们设总共有L个数字可选，D个位置可填，该位填的数字为i，现在填的第step位　　（例子中L=4 D=2）

那么step位填i后，后面可填的方案数为C(L-i,D-step)

如果C>=m，说明这一位就填i，下一位就从i+1开始搜

否则这一位肯定不填i，m-=C后，继续判断该位是否填i+1

这样，我们就可以以近乎O(L)地判断出来第m项了。

Code

  1 #include<set>
  2 #include<map>
  3 #include<queue>
  4 #include<stack>
  5 #include<cstdio>
  6 #include<cstring>
  7 #include<iostream>
  8 #include<algorithm>
  9 #define inf (1<<30)
 10 #define ll long long
 11 #define RG register int
 12 #define rep(i,a,b)    for(RG i=a;i<=b;i++)
 13 #define per(i,a,b)    for(RG i=a;i>=b;i--)
 14 #define maxn 1000005
 15 #define lim  1000002
 16 using namespace std;
 17 ll N,k,cnt,dep,numlim;
 18 int pri[maxn],p[maxn],vis[maxn];
 19 ll rec[1000][1000];
 20 inline ll read()
 21 {
 22     ll x=0,f=1;char c=getchar();
 23     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 24     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 25     return x*f;
 26 }
 27 
 28 void pre()
 29 {
 30     rep(i,2,lim)
 31     {
 32         if(!pri[i])    p[++cnt]=i;
 33         for(RG j=1;j<=cnt&&i*p[j]<=lim;j++)
 34         {
 35             pri[i*p[j]]=1;if(!(i%p[j]))    break;
 36         }
 37     }
 38 }
 39 
 40 ll work(ll x,ll p)
 41 {
 42     ll res=0;
 43     while(x)    res+=x/p,x/=p;
 44     return res;
 45 }
 46 
 47 ll QP(ll a,ll mi)
 48 {
 49     ll ans=1;
 50     while(mi)
 51     {
 52         if(mi&1)    ans*=a;
 53         a*=a;
 54         mi>>=1;
 55     }
 56     return ans;
 57 }
 58 
 59 ll cnm(ll n,ll m)
 60 {
 61     ll ans=1;
 62     for(RG i=1;p[i]<=n;i++)
 63     {
 64         ll _1=work(n,p[i]);
 65         ll _2=work(m,p[i]);
 66         ll _3=work(n-m,p[i]);
 67         ans*=QP(p[i],_1-_2-_3);
 68     }
 69     return ans;
 70 }
 71 
 72 void pt()
 73 {
 74     cout<<1;
 75     rep(i,1,numlim)
 76     {
 77         printf("%d",!vis[i]);
 78     }
 79     exit(0);
 80 }
 81 
 82 void dfs(int step,int st)
 83 {
 84     if(step>dep)
 85     {
 86         pt();
 87         return;
 88     }
 89     for(int i=st;i<=numlim;i++)
 90     {
 91         int nn=numlim-i,mm=dep-step,cc;
 92         if(rec[nn][mm])    cc=rec[nn][mm];
 93         else rec[nn][mm]=cc=cnm(nn,mm);
 94         if(cc<N){N-=cc;continue;}    
 95         vis[i]=1;
 96         dfs(step+1,i+1);
 97         vis[i]=0;
 98     }
 99 }
100 
101 void work()
102 {
103     if(N==1){rep(i,1,k)cout<<1;return;}--N;
104     for(register ll i=k,j=1;;++i,++j)
105     {
106         ll C=cnm(i,j);rec[i][j]=C;
107         if(C>=N) {numlim=i,dep=j;break;}
108         N-=C;
109     }
110     dfs(1,1);
111 }
112 
113 void work1()
114 {
115     cout<<1;rep(i,2,N)    printf("0"); exit(0);
116 }
117 
118 int main()
119 {
120     N=read(),k=read();
121     if(k==1)    work1();
122     pre();
123     work();
124     return 0;
125 }

View Code