一本通1649【例 2】2^k 进制数

1649：【例 2】2^k 进制数

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

原题来自：NOIP 2006 提高组

设 r 是个 2^k 进制数，并满足以下条件：

1、r 至少是个 2 位的 2^k 进制数。

2、作为 2^k 进制数，除最后一位外，r 的每一位严格小于它右边相邻的那一位。

3、将 r 转换为 2 进制数 q 后，q 的总位数不超过 w。

在这里，正整数 k 和 w 是事先给定的。

问：满足上述条件的不同的 r 共多少个？

【输入】

输入只一行，为两个正整数 k 和 w。

【输出】

输出为一行，是一个正整数，为所求的计算结果，即满足条件的不同的 rr 的个数（用十进制数表示，要求最高位不得为 0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。

提示：作为结果的正整数可能很大，但不会超过 200 位。

【输入样例】

3 7

【输出样例】

【提示】

数据范围与提示：

对于所有数据，1≤k≤9,k<w≤3×10⁴ 。

sol：这道其实是道大水题

对于条件二很容易发现是个组合数，而且是严格小于，k的范围也不大，直接n²预处理组合数

统计答案是注意讨论首位是0和非0的情况

Ps：裸的高精貌似会MLE，建议压位

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+'');    return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int Base=,power=;

int K,B,W;

struct Bignum

{

    int a[];

    Bignum(){memset(a,,sizeof a);}

    Bignum(int x)

    {

        memset(a,,sizeof a);

        while(x)

        {

            a[++a[]]=x%Base;

            x/=Base;

        }

        return;

    }

    inline void print()

    {

        int i;

        write(a[a[]]);

        for(i=a[]-;i>=;i--)

        {

            if(a[i]<) putchar('');

            if(a[i]<) putchar('');

            if(a[i]<) putchar('');

            write(a[i]);

        }

        return;

    }

}C[][],ans;

#define P(x) x.print(),putchar(' ')

#define Pl(x) x.print(),putchar('\n')

inline Bignum operator+(const Bignum &p,const Bignum &q)

{

    int i;

    Bignum ans=p;

    for(i=;i<=q.a[];i++)

    {

        ans.a[i]+=q.a[i];

        ans.a[i+]+=ans.a[i]/Base;

        ans.a[i]-=(ans.a[i]>=Base)?Base:;

    }

    while(ans.a[ans.a[]+]) ans.a[]++;

    return ans;

}

int main()

{

    int i,j;

    R(K); R(W);

    B=<<K;

    C[][]=Bignum();

    for(i=;i<=B;i++)

    {

        for(j=;j<=B;j++)

        {

            C[i][j]=C[i][j]+C[i-][j];

            if(j) C[i][j]=C[i][j]+C[i-][j-];

        }

    }

    int oo=W%K,Up=W/K;

    for(i=min(Up,B-);i>=;i--)

    {

        ans=ans+C[B-][i];

    }

    if(oo)

    {

        int Last=(<<oo)-;

        for(i=;i<=Last;i++) if((B-i-)>=Up)

        {

            ans=ans+C[B-i-][Up];

        }

        Pl(ans);

    }

    else

    {

        Pl(ans);

    }

    return ;

}

/*

input

3 7

output

36

input

2 8

output

4

*/

巴特西