2^k进制数-题解（C++代码）

注意事项:求解的答案最大为200位的十进制，longlong不能存下，用数组存，数组中的每个变量都存十位十进制数，计算答案时是高精度加法；

参考代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[30000][512]={0};//a[i][j];i位数，j当前位数下最高位的数字；a[i][j]存的是最高位为j,位数为i，满足条件的数的个数

int main(){

    int k,w;

    ll ans[21]={0};//存答案；

    cin>>k>>w;

    int wl=w/k;//最大2^k制位数

    int ml1=pow(2,k);//每位数可取值限制

    int ml2;//位数最大时最高位的取值限制

    if(w%k!=0){

        wl++;

        ml2=min((int)pow(2,w%k),ml1);

    }

    for(int j=1;j<ml1;j++){//初始化，1位的每个取值个数都为1

        a[1][j]=1;

    }

    int kk=0;

    for(int i=2;i<=wl;i++){//从2位数的个数开始计算

        int ml=ml1;

        if(i==wl)ml=ml2;

        ll t=0;

        for(int j=1;j<ml;j++){//i位，最高位为j

            for(int k=j+1;k<ml1;k++){

                a[i][j]+=a[i-1][k];

            }

            t+=a[i][j];

        }

        ll u=0;

        //10000000000进制的高精度加法

        kk=0;

        ans[kk]+=t;

        while(ans[kk]/10000000000!=0){

            ans[kk+1]+=(ans[kk]/10000000000);

            ans[kk]=ans[kk]%10000000000;

            kk++;

        }

    }

    kk=20;

    while(ans[kk]==0){

        kk--;

    }

    while(kk>=0){

        cout<<ans[kk];

        kk--;

    }

    cout<<endl;

    return 0;

}