题解 P1066 【2^k进制数】组合+进制+高精压位
wjyyy
2018-04-27 19:14:16
这是一道很数学的题（楼下也有用模拟递推跑的），从题目意思来看，就是要求有多少个长为$w$的二进制（$01$）串满足在被转为$2^k$进制之后，满足左边的数严格小于右边。
如下表是一种$k=3,w=7$满足条件的情况
| 二进制 | 1 | 100 | 101 |
| -----------: | -----------: | -----------: | -----------: |
| **$2^3$进制** | **1** | **4** | **5** |
| 二进制位数 |7|6~4|3~1|
|八进制位数|3|2|1|
||最高位||最低位|
题目表达的条件有
1. 转换之后的数至少有$2$位，则$r_{(10)}≥2^k$。
1. 二进制串长度为$w$，但不代表第$w$位上一定是$1$，因此这个二进制串可以是$2-w$的任意长度，所以根据长度来枚举。
1. 如果$w∤(2^k)$，那么这个数的最高位不能取遍$[1,2^k-1]$(不能重复算取$0$的情况，因为取$0$相当于没有最高位，无意义)。
因此我们来看一下当$k=3,w>8$时这种情况从低位向高位处理的过程。
| |… | 第3位 | 第2位 | 第1位 |
| ----------- | ----------- | ----------- | ----------- |
| 可以取到的数的个数 |…| $C^3_7$* | $C^2_7$ | $N/A$ |
| 说明 |…|取3个分别占1,2,3位** | 八进制有7个数,取两个分别占1,2位*** | 不能取1位 |
| 总共取到的数的个数 |…| $C^3_7+C^2_7$ | $C^2_7$ |$N/A$ |
注释：
*每个组合里一个数只可能出现一次，保证了严格单增的条件
**每个组合只算了一次，因为每个组合有且仅有一种顺序使其单增
***因为单增，只能取[1,7]，注意不能取0，也不能取8，因为8要进位
那么如果$w\leq8$呢
我们回到一开始举的例子
$k=3,w=7$
| 包含位数| 1 | 3 | 3 |
| -----------: | -----------: | -----------: | -----------: |
| 取值范围 | {$1$} | $[1,2^3-1]$ | $[1,2^3-1]$ |
这个情况下，最高位只能取1，那么后面的数依照严格单增只能取$[2,2^3-1]$
所以能取到的数有$6$个，{$2,3,4,5,6,7$}
在原来的基础上加上$C^2_6$
其中$2=\lceil \frac {(w-1)}k\rceil+1$
$6=2^k-1-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:
```cpp
#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;
}
```