题解 P1066 【2^k进制数】组合+进制+高精压位

wjyyy · 2018-04-27 19:14:16 · 题解

这是一道很数学的题（楼下也有用模拟递推跑的），从题目意思来看，就是要求有多少个长为w的二进制（01）串满足在被转为2^k进制之后，满足左边的数严格小于右边。

如下表是一种k=3,w=7满足条件的情况

题目表达的条件有

1. 转换之后的数至少有2位，则r_{(10)}≥2^k。
2. 二进制串长度为w，但不代表第w位上一定是1，因此这个二进制串可以是2-w的任意长度，所以根据长度来枚举。
3. 如果w∤(2^k)，那么这个数的最高位不能取遍[1,2^k-1](不能重复算取0的情况，因为取0相当于没有最高位，无意义)。

因此我们来看一下当k=3,w>8时这种情况从低位向高位处理的过程。

注释：

*每个组合里一个数只可能出现一次，保证了严格单增的条件

**每个组合只算了一次，因为每个组合有且仅有一种顺序使其单增

***因为单增，只能取[1,7]，注意不能取0，也不能取8，因为8要进位

那么如果w\leq8呢

我们回到一开始举的例子

这个情况下，最高位只能取1，那么后面的数依照严格单增只能取[2,2^3-1]

所以能取到的数有6个，{2,3,4,5,6,7} 在原来的基础上加上C^2_6

其中2=\lceil \frac {(w-1)}k\rceil+1

同时因为高精除法太烦人了时间效率问题，我们可以提前把用到的C_i^j利用杨辉三角存一下，并且imax=2^k这样高精就只用写加法了。

上面提到imax=2^k，但实际上数组层数开的不是2^9（kmax=9），而是2^10，因为杨辉三角会多那么一层。但根据这个题的测试点，开600即可AC

正常的杨辉三角要注意，当使用C_i^j时，要调用a[i+1][j+1]，也可以提前从[0][0]处理一下

Code:

#include<cstring>
#include<cstdio>
int max(int x,int y){return x>y?x:y;}
struct lll//高精要压位，不然拖低时间效率，这个题计算量也很大
{
    int num[52];
    lll(int x)
    {
        memset(num,0,sizeof(num));
        if(x==0)
            return;
        int k=0;
        while(x)
        {
            k++;
            num[k]=x%10000;
            x/=10000;
        }
        num[0]=k;
    }
    lll()
    {
        memset(num,0,sizeof(num));
    }
    friend lll operator +(lll a,lll b)
    {
        a.num[0]=max(a.num[0],b.num[0])+1;
        for(int i=1;i<=a.num[0];i++)
        {
            a.num[i]+=b.num[i];
            if(a.num[i]>=10000)
            {
                a.num[i+1]++;
                a.num[i]-=10000;
            }
        }
        while(a.num[0]>0&&a.num[a.num[0]]==0)
            a.num[0]--;
        return a;
    }
};
lll a[620][620];
void print(lll x)
{
    for(int i=x.num[0];i>0;i--)
    {
        if(i!=x.num[0])
        {
            if(x.num[i]<1000)
                printf("0");
            if(x.num[i]<100)
                printf("0");
            if(x.num[i]<10)
                printf("0");
        }
        printf("%d",x.num[i]);
    }
    printf("\n");
}
int main()
{
    int k,w;
    scanf("%d%d",&k,&w);
    int t=(w-1)/k+1;//t是转化为2^k进制数后的位数（包括不确定的一位）
    lll one(1);
    for(int i=1;i<=(1<<k)+1;i++)//为了杨辉三角的调用，需要多做一层
    {
        a[i][1]=one;
        a[i][i]=one;
        for(int j=2;j<i;j++)
            a[i][j]=a[i-1][j-1]+a[i-1][j];
    }
    /*for(int i=1;i<=(1<<k)+1;i++)
    {
        for(int j=1;j<=i;j++)
        {
            print(a[i][j]);
            printf(" ");
        }
        printf("\n");
    }*///这里是打印杨辉三角，检验是否正确
    lll sum(0);
    for(int i=2;i<t;i++)
        sum=sum+a[(1<<k)-1 +1][i +1];//+1是杨辉三角性质的要求
        //是(1<<k)-1个里选2个而不是8个里选，要格外注意
    w=(w-1)%k+1;
    for(int i=1;i<(1<<w);i++)
        sum=sum+a[(1<<k)-i-1 +1][t-1 +1];//
    print(sum);
    return 0;
}