洛谷1066 2^k进制数

题意

求一个位数 $\geq 2$ 的 $2^{k}$ 进制数 $r$ ，满足：

1. 化为二进制后位数 $\le w$
2. 每一位上的数依次递增

其中 $k\le 9 \ , \ k\le w\le 30000$ ，保证 $r$ 化为 $10$ 进制的位数 $\le 200$ 。

题解

对于条件 $1$ ，显然 $r$ 的位数 $L \le \lceil \dfrac{w}{k}\rceil $ 。

当 $L\le \lfloor \dfrac{w}{k} \rfloor$ 时，每一位可以任意取。可以枚举位数 $i$ ，问题就等价为：从 $2^{k}-1$ 个数中选 $i$ 个数的方案数，答案即为

$$C_{2^{k}-1}^i \tag{1}$$

当 $L=\lfloor \dfrac{w}{k} \rfloor +1$ 时，显然对于每一位上可以取的数是由限制的。

先考虑把后 $L-1$ 位随便取，那么第一位 $x$ 的二进制应该满足位数

$$Len_x\le w-\lfloor \dfrac{w}{k} \rfloor\times k$$

即

$$Len_x\le w \ mod \ k$$

也就是说

$$x\le 2^{w \ mod \ k}-1$$

那么可以在 $\left[ 1,2^{w \ mod \ k}-1\right]$ 的范围内枚举首位 $x$ ，可以取的数字的个数为 $(2^{k}-1)-2^{w \ mod \ k}$ 。答案即为

$$C_{(2^{k}-1)-2^{w \ mod \ k}}^{L}\tag{2}$$

$(1)+(2)$ 即为答案。

显然需要用高精。可以预处理一下组合数，这样就不用乘法和除法。

#include<bits/stdc++.h>

using namespace std;

struct bigint {
    short len,s[205];
    bigint(){ len=0; memset(s,0,sizeof(s)); }
} C[512][512],ans;
int k,w,K;

inline bigint add(bigint &x,bigint &y)
{
    bigint z;
    int len=max(x.len,y.len),add=0;
    for (int i=1;i<=len;i++)
    {
        z.s[i]=x.s[i]+y.s[i]+add;
        add=z.s[i]/10;
        z.s[i]%=10;
    }
    if (add) z.s[++len]=add;
    z.len=len;
    return z;
}

inline void print(bigint &x) { for (int i=x.len;i;i--) printf("%d",x.s[i]); }

inline void one(bigint &x) { x.len=1; x.s[1]=1; }

inline void get_C()
{
    one(C[0][1]); one(C[1][1]);
    for (int i=2;i<=K;i++)
    {
        one(C[0][i]);
        for (int j=1;j<=i;j++) C[j][i]=add(C[j-1][i-1],C[j][i-1]);
    }
}

int main()
{
    scanf("%d%d",&k,&w);
    K=(1<<k)-1;
    get_C();
    int L=w/k;
    int mxlen=min(K,L);
    for (int i=2;i<=mxlen;i++) ans=add(ans,C[i][K]);
    if (w%k==0) return print(ans),0;
    int mxfirst=min((1<<(w%k))-1,K-L);
    for (int i=1;i<=mxfirst;i++) ans=add(ans,C[L][K-i]);
    return print(ans),0;
}