牛客假日团队赛16

比赛链接
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