2^k进制数
云巨

在这里我要感谢小云巨巨给我提供的思路和题~(云巨V587~//皮一下很爽~逃~)

这道题大体思路是这样的,首先 2^k进制数转化位二进制数会在原来的位数上*k

这里我们就拿 2^3进制数也就是八进制数来举例把

比如说7这个数在八进制数表示下就是7 一位数
但是在二进制表示形式下就是111 也就是3位数

因为题中描述说我们2^k进制数转化为2进制数不能超过w位 那也就是说 我们可以对二进制数的总位w 来做变换 因为对应的2^k进制数 那么在2^k进制数下前w/k位 我们是一定可以填满的,剩下的w%k位我们是构不成一个2^k进制数位的
因此我们只需要枚举前w/k每一位能填1<<k-1而且满足题意得情况在加上剩下得一位满足得情况就可以了
剩下一位要满足情况得条件是什么呢?
如果我在这一位填入得数是x 这个x转化成二进制位是不是一定要小于等于w%k吖
如果超过w%k那我们转化得二进制数位要进位 那整体转化二进制数位要大于w了所以不满足题意
所以对于最后一位我们只需要枚举1~1<<(w%k)-1这些数可以产生得情况就好了

好了balabala了这么多接下来就该看看代码怎么实现了

首先我们可以定义一个二维数组 也就是动态规划数组 f[i][j]它所表示的是我第i位填j的满足情况的方案数

f[i][j]=f[i-1][j+1]+f[i-1][j+2]+f[i-1][j+3]+.........+f[i-1][1<<k-1]
推到了这里我们要做一个优化 这也就是我们为什么要逆着推的过程
逆着推:
那上一次更新的是
f[i][j+1]=f[i-1][j+2]+f[i-1][j+3]+.....+f[i-1][1<<k-1]
大家惊奇的发现 f[i][j]的后面部分与f[i][j+1]是相等的
所以 f[i][j]=f[i][j+1]+f[i-1][j+1]
大家看这个式子如果我正推 我在更新第j这个数的时候用的是第j+1的值 由于是正的枚举1<<k-1我j+1的值还没有被更新
答案就会少一些情况
如果大家非要正的推其实也是可以的
如果非要正的推我们就不做优化当枚举到f[i][j]时候我们就
直接统计f[i-1][j+1]+f[i-1][j+2]+f[i-1][j+3]+.........+f[i-1][1<<k-1]这些情况就好了
又balabala了这么多 现在就呈现代码啦~
由于数据问题这里采用了压位高精度~

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e4+10,M=510;
const int P=1e8;

int k,w;

struct nkl
{
    int w[55];
    int len;

    nkl()
    {
        memset(w,0,sizeof(w));
        len=0;
    }

    void build(int q)
    {
        w[0]=q;
        len=1;
    }

    void print()
    {
        printf("%d",w[len-1]);
        for (int i=len-2;i>=0;i--)
            printf("%08d",w[i]);
    }

    nkl operator + (const nkl x)
    {
        nkl y;
        y.len=max(len,x.len);
        for (int i=0;i<y.len;i++)
        {
            y.w[i]+=w[i]+x.w[i];
            if(y.w[i]>P)
            {
                y.w[i+1]+=y.w[i]/P;
                y.w[i]%=P;
            }
            if(y.w[y.len]>0) y.len++;
        }

        return y;
    }
}f[N/10][M],ans;

int main()
{
    scanf("%d%d",&k,&w);
    int num=w/k,rem=w%k;
    if(num==0) puts("0");
    else
    {
        int li=1<<k;
        for (int i=li-1;i>=1;i--) f[1][i].build(1);

        for (int i=2;i<=num;i++)
            for (int j=li-1;j>=1;j--)
                f[i][j]=f[i][j+1]+f[i-1][j+1],ans=ans+f[i][j];

        for (int i=li-1;i>=1;i--)
            f[num+1][i]=f[num][i+1]+f[num+1][i+1];
        for (int i=(1<<rem)-1;i>=1;i--)
            ans=ans+f[num+1][i];

        ans.print();
    }

    return 0;
}

这是正的推

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e4+10,M=510;
const int P=1e8;//压位高精 

int k,w;

struct nkl
{
    int w[55];
    int len;

    nkl()
    {
        memset(w,0,sizeof(w));
        len=0;
    }

    void build(int q)
    {
        w[0]=q;
        len=1;
    }

    void print()
    {
        printf("%d",w[len-1]);
        for (int i=len-2;i>=0;i--)
            printf("%08d",w[i]);
    }

    nkl operator + (const nkl x)
    {
        nkl y;
        y.len=max(len,x.len);
        for (int i=0;i<y.len;i++)
        {
            y.w[i]+=w[i]+x.w[i];
            if(y.w[i]>P)
            {
                y.w[i+1]+=y.w[i]/P;
                y.w[i]%=P;
            }
            if(y.w[y.len]>0) y.len++;
        }

        return y;
    }
}f[N/10][M],ans;

int main()
{
    scanf("%d%d",&k,&w);
    int num=w/k,rem=w%k;
    //多少位,还余多少位
    if(num==0) puts("0");
    else
    {
        int li=1<<k;
        for (int i=li-1;i>=1;i--) f[1][i].build(1);

        for (int i=2;i<=num;i++)
            for (int j=1;j<=li-1;j++)
            {
                for (int p=j+1;p<=li-1;p++)
                    f[i][j]=f[i][j]+f[i-1][p];
                ans=ans+f[i][j];
            }

        for (int i=1;i<=(1<<rem)-1;i++)
        {
            for (int p=i+1;p<=li-1;p++)
                f[num+1][i]=f[num+1][i]+f[num][p];
                ans=ans+f[num+1][i];
        }


        ans.print();
    }
    return 0;
}