分两种情况：$k|n$和$k$不整除$n$
如果$k|n$，那么长度为$n$的二进制数就能被恰好分成$n/k$个块；所以若某个数长度是$x$个块，由于每个块内能填不同的$2^k-1$个数，那么就有$C_{2^k-1}^{x}$
所以整除时答案是$sum_{i=2}^{n/k} space C_{2^k-1}^{i}$
如果$k$不整除$n$,那么一共会分成$lfloor frac{n}{k} floor+1$块,而最后一个不完整的块只有$n ext{mod} k$位，能选择的数还是$0$到$2^{n ext{ } ext{mod} ext{ }k}-1$
如果这个最高位选择填$0$那么回到了$k|n$的情况，所以最高位填0的方案数为$sum_{i=2}^{left lfloorfrac{n}{k} ight floor} C_{2^k-1}^{i}$
之后最高位还可以填$1$到$2^{n ext{ } ext{mod} ext{ }k}-1$，如果我们选择填$i$的话，那么后面的块内要填比$i$大的数，所以剩下的每个块内可以填的就有$2^k-1-i$个数，所以方案数就是$C_{2^k-1-i}^{left lfloorfrac{n}{k} ight floor}$
所以最后的答案还应该加上$sum_{i=1}^{2^{n ext{ } ext{mod} ext{ }k} space space space -1} space C_{2^k-1-i}^{left lfloorfrac{n}{k} ight floor}$
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cctype> #include<cstdlib> #include<vector> #include<map> #include<set> #define ll long long #define R register int static char B[1<<15],*S=B,*D=B; #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++) using namespace std; inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } short c[210]; int n,k,p,res,t; inline string add(string a,string b) { R lena=a.size(),lenb=b.size(); reverse(a.begin(),a.end()),reverse(b.begin(),b.end()); memset(c,0,sizeof(c)); R p=0; for(;p<max(lena,lenb)||c[p];++p) c[p]+=(int)(p<lena?1:0)*(a[p]-48)+(int)(p<lenb?1:0)*(b[p]-48),c[p+1]+=c[p]/10,c[p]%=10; string ret=" "; for(R i=p-1;~i;--i) ret.insert(ret.end(),char(c[i]+48)); reverse(a.begin(),a.end()),reverse(b.begin(),b.end()); return ret; } string ans; string C[512][512]; signed main() { k=g(),n=g(),p=n/k,res=n%k; t=(1<<k)-1,C[0][0]="1"; for(R i=1;i<=t;++i) { C[i][0]="1"; for(R j=1;j<i;++j) C[i][j]=add(C[i-1][j],C[i-1][j-1]); C[i][i]="1"; } for(R i=2;i<=p;++i) { if(i>t) break; ans=add(ans,C[t][i]); } R lim=(1<<res)-1; for(R i=1;i<=lim;++i) { if(p>t-i) break; ans=add(ans,C[t-i][p]); } cout<<ans<<endl; }
2019.06.05