普通dp(80pts)

f[i][j]表示第i位大于等于$j$的方案数的和，从后往前递推

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1<<10;
int k,w,n,m,p;
LL f[N];
void run()
{
    for(int j=m-1;j>=1;j--)  //前缀和：f[j] = sum(f[j], f[j+1], ..., f[m-1])
    {
        f[j]=f[j]+f[j+1];
    }
}
int main()
{
    cin>>k>>w;
    n=w/k;
    m=1<<k; //每位数字的最大值
    p=(1<<(w%k))-1;//最高位的最大值
    for(int i=1;i<m;i++) f[i]=1;//长度为1的时候，每个数字可以作为最后一段
    run();//第一次运行后,f[i]表示以大于等于i结尾的长度为2的数的个数
    LL ans=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<m;j++) f[j]=f[j+1];//去掉最小的数字
        run();//更新f数组,得到长度i+1的数的分布
        ans=ans+f[1];//f[1]表示以大于等于1结尾的长度是i+1的数字
    }
    //处理剩余位
    for(int i=1;i<=p;i++) ans=ans+f[i+1];
    cout<<ans;
}

普通组合数(80pts)

当转成的数是$a$位，那么等价于 $1 \leq x_1< x_2 <x_3...x_a \leq x^k-1$

也就是$C_{2^k-1}^2$,然后如果最高位有余数，也就是有不合法的选择，我们减去不合法的选择($2^b \leq x_1< x_2 <x_3...x_a \leq x^k-1$)即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL C(LL a,LL b) //阶乘
{
    LL res=1;
    for(int i=a,j=1;j<=b;i--,j++)
    {
        res=res*i/j;
    }
    return res;
}
int main()
{
    int k,w;
    cin>>k>>w;
    int n=(w+k-1)/k,b=w%k; //求位数长度和最高位的二进制长度
    LL res=0;
    for(int i=2;i<=n&&i<(1<<k);i++) //枚举位数
    {
        res+=C((1<<k)-1,i);
        if(i==n&&b) res-=C((1<<k)-(1<<b),i); //减去最高位不合法的状态
    }
    cout<<res;
    return 0;
}

高精度组合数

#include<bits/stdc++.h>
using namespace std;
const int N=210;
void add(int a[],int b[]) //高精度加法 
{
	for(int i=0,t=0;i<N;i++)
	{
		a[i]=a[i]+b[i]+t;
		t=a[i]/10;
		a[i]%=10;
	}
}
void sub(int a[],int b[]) //高精度减法
{
	for(int i=0,t=0;i<N;i++)
	{
		a[i]=a[i]-b[i]+t;
		if(a[i]<0) a[i]+=10,t=-1;
		else t=0; 
	}
}
void mul(int a[],int b) //高精度乘法
{
	for(int i=0,t=0;i<N;i++)
	{
		t+=a[i]*b;
		a[i]=t%10;
		t/=10;
	}
}
void div(int a[],int b) //高精度除法
{
	for(int i=N-1,t=0;i>=0;i--)
	{
		t=t*10+a[i];
		a[i]=t/b;
		t%=b; 
	}
}
void C(int tmp[],int a,int b) //组合数
{
	memset(tmp,0,N*4);
	tmp[0]=1; //初始化
	for(int i=a,j=1;j<=b;i--,j++)
	{
		mul(tmp,i);
		div(tmp,j);
	}
}
int main()
{
	int k,w;
	cin>>k>>w;
	int n=(w+k-1)/k,b=w%k; //计算位数和最高位可能存在的长度
	int res[N]={0},tmp[N];
	for(int i=2;i<=n&&i<(1<<k);i++) //枚举数的长度
	{
		C(tmp,(1<<k)-1,i);
		add(res,tmp); //累加
		if(i==n&&b) //需要去除非法状态
		{
			C(tmp,(1<<k)-(1<<b),i);
			sub(res,tmp);
		}
	}
	int lenc=N-1; //高精度输出结果
	while(lenc&&res[lenc]==0) lenc--;
	for(int i=lenc;i>=0;i--)
	{
		cout<<res[i];
	}
	return 0;
}