[NOIP 2006 提高组] 2^k 进制数

知识点

组合计数、二进制位数、高精度

解题思路

设B=2^k，选出的数位必须是1到B-1中的递增子集。完整长度len满足len·k≤w时计C(B-1,len)。若w=qk+r且r>0，还可选长度q+1的数：枚举首位d≤2^r-1，后面选q个大于d的数位，计C(B-1-d,q)。只统计至少两位。

正确性说明

递增且无前导零的数位串与非零数位子集一一对应。完整长度的数均满足位数限制；部分最高段只有r位，等价于首位受上界2^r-1约束。按长度和首位划分的情况互斥穷尽，相加即答案。组合数以乘除递推精确求得。

易错点

总长度可能不足两位，此时为0；最高位不能取0；w很大时最长仅B-1位；答案用高精度。

复杂度

B≤512；O(B²)次小整数高精度乘除，空间O(B)个数位量级。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Big{static const int B=10000;vector<int>d;Big(long long x=0){do{d.push_back(x%B);x/=B;}while(x);}void trim(){while(d.size()>1&&d.back()==0)d.pop_back();}bool operator<(const Big&o)const{if(d.size()!=o.d.size())return d.size()<o.d.size();for(int i=(int)d.size()-1;i>=0;i--)if(d[i]!=o.d[i])return d[i]<o.d[i];return false;}Big operator+(const Big&o)const{Big r;r.d.assign(max(d.size(),o.d.size())+1,0);int carry=0;for(int i=0;i<(int)r.d.size();i++){int v=carry+(i<(int)d.size()?d[i]:0)+(i<(int)o.d.size()?o.d[i]:0);r.d[i]=v%B;carry=v/B;}r.trim();return r;}Big operator*(const Big&o)const{vector<long long>v(d.size()+o.d.size()+1);for(int i=0;i<(int)d.size();i++)for(int j=0;j<(int)o.d.size();j++)v[i+j]+=1LL*d[i]*o.d[j];Big r;r.d.resize(v.size());for(int i=0;i<(int)v.size();i++){if(i+1<(int)v.size())v[i+1]+=v[i]/B;r.d[i]=v[i]%B;}r.trim();return r;}Big operator*(int x)const{return *this*Big(x);}Big operator/(int x)const{Big r=*this;long long rem=0;for(int i=(int)d.size()-1;i>=0;i--){long long v=rem*B+d[i];r.d[i]=v/x;rem=v%x;}r.trim();return r;}friend ostream&operator<<(ostream&os,const Big&a){os<<a.d.back();for(int i=(int)a.d.size()-2;i>=0;i--)os<<setw(4)<<setfill('0')<<a.d[i];return os;}};

Big choose(int n,int k){if(k<0||k>n)return Big();k=min(k,n-k);Big x(1);for(int i=1;i<=k;i++)x=x*(n-i+1)/i;return x;}int main(){int k,w;cin>>k>>w;int B=1<<k,q=w/k,r=w%k;Big ans,cur(1);for(int len=1;len<B;len++){cur=cur*(B-len)/len;if(len>=2&&len<=q)ans=ans+cur;}if(r&&q>=1&&q+1<B)for(int d=1;d<(1<<r);d++)ans=ans+choose(B-1-d,q);cout<<ans<<'\n';}