普通组合数(80pts)

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

也就是$C_{2^k-1}^2$,然后如果最高位有余数，也就是有不合法的选择，我们减去不合法的选择即可。

#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;
}