比赛链接
https://ac.nowcoder.com/acm/contest/1089#question
B题题解
分两部分考虑。
第一部分，只有个完整的位的填法。
因为最高位要从1开始，而后面的每一位都需要递增，所以每一位都有种填法。同时假设r有i位，那么填法数就是
。于是总的填法数就是
种。
第二部分，最高位（不完整位）的填法。
假设最高位填的数字为i，那么i的范围是。而后面完整的位有
个。这些位的选择范围是
。因此当最高位数字为i时，对答案的贡献是
。总的填法数就是
种。
需要额外注意的是，最高位数字为i时，后面的数字只能大于i，所以总共有种数字。因此要保证
。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxl=200+5;
const int maxn=512+5;
const int INF=0x3f3f3f3f;
struct bigint{
int n,a[maxl];
bigint(){n=0;memset(a,0,sizeof(a));}
int& operator[](int x){return a[x];}
void print(){for(int i=n;i>=1;i--) cout<<a[i];}
friend bigint operator+(bigint x,bigint y){
bigint res;res.n=max(x.n,y.n);
for(int i=1;i<=res.n;i++) res.a[i]=x.a[i]+y.a[i];
for(int i=1;i<=res.n;i++) res.a[i+1]+=res.a[i]/10,res.a[i]%=10;
if(res[res.n+1]) res.n++;
return res;
}
};
bigint c[maxn][maxn];
bigint ans;
int k,w;
void pre(){
c[0][0].n=1,c[0][0].a[1]=1;
for(int i=1;i<=maxn-5;i++) for(int j=0;j<=i;j++){
if(j==0){
c[i][j].n=1,c[i][j].a[1]=1;
}
else c[i][j]=c[i-1][j-1]+c[i-1][j];
}
ans.n=1,ans.a[1]=0;
}
void solve(){
for(int i=2;(i<=w/k);i++) ans=ans+c[(1<<k)-1][i]; //因为各位不相同 所以r最多只有i<(1<<k)-1种数字 因此要控制i<(1<<k)
for(int i=1;(i<=(1<<(w%k))-1);i++) if((1<<k)-i>=w/k) ans=ans+c[(1<<k)-i-1][w/k];
//与上同理 最高位数字为i是 后面的数字只能大于i 所以总共有w/k+i种数字 因此要保证w/k+i<=(1<<k)
}
int main() {
ios::sync_with_stdio(false);
// freopen("2^k进制数.in","r",stdin);
cin>>k>>w;
pre();
solve();
ans.print();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
