Link

题目描述

设 \(S\) 是长度为 \(w\) 的 \(01\) 串。从串的右边开始，每 \(k\) 个字符分成一段（最后不够 \(k\) 个字符的也分成一段），组成一个小于 \(2^k\) 的数。然后这 \(\left\lceil\frac{w}{k}\right\rceil\) 个数将组成一个序列。若这个序列除去前导零后的长度不小于 \(2\) 且序列里的数严格递增，那么 \(S\) 就是一个合法的串。求所有合法的串的个数。

解法

计数题。一开始就往组合方面想了。这个直觉似乎是对的。

先除去第一个数不看，即强制选 \(0\)（因为它可能不是 \(2^k\)，比较特殊），那么对于后面的 \(\lfloor \frac{w}{k} \rfloor\) 个数，如果直接取的话，每个数都可以取 \(0\) ~ \(2^p-1\)，要满足严格递增，实际上就是在这 \(2^p\) 个数里面选 \(\lfloor \frac{w}{k} \rfloor\) 个来组成序列，那么方案就是

\[\binom{2^p}{\lfloor \frac{w}{k} \rfloor} \]

这样对吗？你会发现这是错的。因为可以有前导零，而且前导零并不是单增的。这就提示我们将前导零抛开，分步计算。现枚举一个 \(i\) ，强制后 \(i\) 个数不为 \(0\)，有 \(2^k-1\) 种，前面剩下的数全部是 \(0\)，有 \(1\) 种，那么总方案数实际上是

\[\sum_{i=2}^{\lfloor \frac{w}{k} \rfloor} \binom{2^k-1}{i} \]

(序列长度大于等于 \(2\) ，\(i\) 要从 \(2\) 开始枚举)
现在将第一个数不为 \(0\) 的方案加进来，枚举 \(i\) 表示第一个数选什么，那么对于后面 \(\lfloor \frac{w}{k} \rfloor\) 个数，就在大于 \(i\) 的数里面选。方案就有

\[\sum_{i=1}^{2^{b \bmod k}} \binom{2^k-1-i}{\lfloor \frac{w}{k} \rfloor} \]

答案就是

\[\sum_{i=2}^{\lfloor \frac{w}{k} \rfloor} \binom{2^k-1}{i} + \sum_{i=1}^{2^{b \bmod k}} \binom{2^k-1-i}{\lfloor \frac{w}{k} \rfloor} \]

考虑怎么求这个东西，我们发现 \(k\) 是一个很小的数，而对于 \(n<m\) ，\(\binom{n}{m}=0\)，所以只需要预处理出 \(n<2^9\) 以内的组合数，用公式直接递推即可。

Tips

推完式子之后发现要写高精，长度范围在 \(200\) 以内。然后写了高精加之后，直接交了，全部 \(MLE\)。一算空间 \(2^9\times 2^9\times 200\times 4\approx 200 MB\)。然后我就想这道题不能预处理，就开始写暴力求组合数（以及高精乘和高精除）。写到一半觉得不可能有这么麻烦，就去翻题解，发现某大佬用的 \(string\) 来存的高精数组。得到启发后，将 \(int\) 换成了 \(char\)，空间直接减成 \(50MB\)。一发过了。

Code

（加了一些边界判定，感性理解即可）

#include<stdio.h>
#include<string.h>
#define N (1<<9)

int n,k;

inline int max(int x,int y){return x>y? x:y;}
struct Big{
    char num[201],len;
    Big(int x=0){memset(num,0,sizeof(num)); len=0; while(x) num[++len]=x%10,x/=10;}
    Big operator +(const Big x){
        Big c; int cur=0;
        c.len=max(x.len,len);
        for(int i=1;i<=c.len;i++){
            c.num[i]+=num[i]+x.num[i]+cur;
            cur=c.num[i]/10;
            c.num[i]%=10;
        }
        if(cur) c.num[++c.len]=cur;
        return c;
    }
    inline void print(){
        for(int i=len;i>=1;i--)
            printf("%d",num[i]);
    }
}C[N][N];

inline int min(int x,int y){return x<y? x:y;}
int main(){
    scanf("%d%d",&k,&n);
    for(int i=0;i<512;i++) C[i][0]=Big(1),C[i][i]=Big(1);
    for(int i=1;i<512;i++)
        for(int j=1;j<i;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
    if(k>=n) printf("0");
    else{
        Big ans=Big(0);
        int p=1<<k; int rg=min(n/k,p-1);
        for(int i=2;i<=rg;i++)
            ans=ans+C[p-1][i];
        if(n%k&&p-1>n/k){
            int p_=1<<(n%k);
            for(int i=1;i<p_&&p-i-1>=n/k;i++)
                ans=ans+C[p-i-1][n/k];
        }
        ans.print();
    }
}
// 3 7