2^k 进制数

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3832 字
统计满足条件的2^k进制数r的个数：至少2位
一本通
例
正文

/*
原题：T1649「一本通 6.6 例 2」2^k 进制数
题意：统计满足条件的 2^k 进制数 r 的个数：至少 2 位；除末位外每位严格小于右邻位；
转成二进制后总位数不超过 w。
思路：各位单调严格递增且首位非 0，故每位只能从 1..2^k-1 中取。
设 r 位，非首位各占 k 个二进制位，则首位最多占 rem=w-(r-1)·k 位。
首位允许值个数 L：rem≥k 时 L=2^k-1，否则 L=2^rem-1。
对首位 d 有 C(2^k-1-d, r-1) 种取法，由曲棍球杆恒等式求和得
本位答案为 C(2^k-1, r) - C(2^k-1-L, r)，对 r=2..rmax 累加。
复杂度：时间 O(rmax·(精度位数))，空间 O(精度位数)
易错点：1) 结果可超 200 位，必须用高精度，不能直接用整数类型；
2) 只有 rem>0 的 r 才合法，且 r 不能超过 2^k-1（可用开头值个数）；
3) 组合数递推用 res=res·(n-r+i)/i 逐步整除，每步都是整除，不用分数。
*/
#include <bits/stdc++.h>
using namespace std;
const int BASE=10000;
struct Big{
    vector<int> d;
    Big(long long v=0){
        if(v==0){
            d.push_back(0);
        }else{
            while(v>0){
                d.push_back(v%BASE);
                v/=BASE;
            }
        }
    }
    void trim(){
        while(d.size()>1 && d.back()==0){
            d.pop_back();
        }
    }
};
Big addBig(const Big& x,const Big& y){
    Big r;
    size_t n=max(x.d.size(),y.d.size())+1;
    r.d.assign(n,0);
    for(size_t i=0;i<x.d.size();i++){
        r.d[i]+=x.d[i];
    }
    for(size_t i=0;i<y.d.size();i++){
        r.d[i]+=y.d[i];
    }
    int carry=0;
    for(size_t i=0;i<r.d.size();i++){
        long long cur=(long long)r.d[i]+carry;
        r.d[i]=cur%BASE;
        carry=cur/BASE;
    }
    r.trim();
    return r;
}
Big subBig(const Big& x,const Big& y){
    Big r;
    r.d.assign(x.d.size(),0);
    for(size_t i=0;i<x.d.size();i++){
        r.d[i]=x.d[i];
    }
    for(size_t i=0;i<y.d.size();i++){
        r.d[i]-=y.d[i];
    }
    long long borrow=0;
    for(size_t i=0;i<r.d.size();i++){
        long long cur=(long long)r.d[i]-borrow;
        if(cur<0){
            cur+=BASE;
            borrow=1;
        }else{
            borrow=0;
        }
        r.d[i]=cur;
    }
    r.trim();
    return r;
}
Big mulSmall(const Big& x,long long m){
    Big r;
    size_t n=x.d.size()+40;
    vector<long long> tmp(n,0);
    for(size_t i=0;i<x.d.size();i++){
        long long cur=(long long)x.d[i]*m;
        size_t j=i;
        while(cur>0 && j<n){
            tmp[j]+=cur%BASE;
            cur/=BASE;
            j++;
        }
    }
    r.d.assign(n+2,0);
    long long carry=0;
    for(size_t i=0;i<n+2;i++){
        long long cur=(i<n?tmp[i]:0)+carry;
        r.d[i]=cur%BASE;
        carry=cur/BASE;
    }
    while(carry>0){
        r.d.push_back(carry%BASE);
        carry/=BASE;
    }
    r.trim();
    return r;
}
Big divSmall(const Big& x,int m){
    Big r;
    r.d.assign(x.d.size(),0);
    long long rem=0;
    for(size_t i=x.d.size();i-- >0;){
        long long cur=rem*BASE+x.d[i];
        r.d[i]=cur/m;
        rem=cur%m;
    }
    r.trim();
    return r;
}
Big comb(long long n,int r){
    if(r<0 || n<r){
        return Big(0);
    }
    if(r==0){
        return Big(1);
    }
    Big res(1);
    for(int i=1;i<=r;i++){
        res=mulSmall(res,n-r+i);
        res=divSmall(res,i);
    }
    return res;
}
void printBig(const Big& x){
    cout<<x.d.back();
    for(int i=(int)x.d.size()-2;i>=0;i--){
        cout<<setw(4)<<setfill('0')<<x.d[i];
    }
    cout<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long k,w;
    cin>>k>>w;
    long long maxv=(1LL<<k)-1;
    if(maxv<2){
        cout<<0<<"\n";
        return 0;
    }
    long long rmax=(w-1)/k+1;
    if(rmax>maxv){
        rmax=maxv;
    }
    Big ans(0);
    for(long long r=2;r<=rmax;r++){
        long long rem=w-(r-1)*k;
        if(rem<=0){
            continue;
        }
        long long lead;
        if(rem>=k || rem>=62){
            lead=maxv;
        }else{
            lead=(1LL<<rem)-1;
        }
        if(lead>maxv){
            lead=maxv;
        }
        Big total=comb(maxv,(int)r);
        Big bad=comb(maxv-lead,(int)r);
        ans=addBig(ans,subBig(total,bad));
    }
    printBig(ans);
    return 0;
}
2^k 进制数

正文

一本通·提高篇的其它内容
