| 记录编号 |
269082 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOIP 2006]2^k进制数 |
最终得分 |
100 |
| 用户昵称 |
 Go灬Fire |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.014 s |
| 提交时间 |
2016-06-13 08:02:28 |
内存使用 |
23.37 MiB |
显示代码纯文本
/*2^k进制数(题解)
作者：李晓涵、许子康
来源：2016小假期集训--第一次检测
大力感谢支持此题解的周游童鞋
题目描述（http://hzoi.openjudge.cn/ceyan/T019/）：
设r是个2^k 进制数，并满足以下条件：
（1）r至少是个2位的2^k 进制数。
（2）作为2^k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。
（3）将r转换为2进制数q后，则q的总位数不超过w。
在这里，正整数k（1≤k≤9）和w（k<W≤30000）是事先给定的
输入只有1行，为两个正整数，用一个空格隔开：k w
输出为1行，是一个正整数，为所求的计算结果要求最高位不得为0
（提示：作为结果的正整数可能很大（高精度加法），但不会超过200位）
样例读入：3 7
样例输出： 36
分析：
首先，此题位数极大，高精度必然需要，要求童鞋们熟练掌握高精加算法。
然后，因为长度为w，所以有w/k个完整的2k进制位（称之为完位），其中每一位都可以表示1~~2k-1中任何一个数。还有1个不完整的2k进制位（称之为残位），这个位数由w%k个二进制位组成，故可以表示1~2w%k-1。
其中，完整的2k进制位与残位需要单独处理，可以先不考虑残位。
1. 处理完位：
据分析知有w/k个完位，例：k=3,w=13时，可以有4个完整的8进制位，可以得到如下表格：
当k=3,w=13时，可以有4个完整的8进制位，可以得到如下表格：
高位>=7 高位>=6 高位>=5 高位>=4 高位>=3 高位>=2 高位>=1
一位 1 2 3 4 5 6 7
两位 1 3 6 10 15 21
三位 1 4 10 20 35
四位 1 5 15 35
为了方便处理我们将其左对齐，进行打表： c[i]=c[i]+c[i-1]
数组下标 c[1] c[2] c[3] c[4] c[5] c[6] c[7]
一位 1 2 3 4 5 6 7
两位 1 3 6 10 15 21
三位 1 4 10 20 35
四位 1 5 15 35
据分析可得到方程方案数c[i]= c[i-1]+未更新的c[i] ，完整部分的的答案是的每一个确定位数高位>=1的方案数之和，即每行的最后一个数的加和,
即对于第i位：ans+=c[2k-1-i+1];
2. 处理残位：
据分析知残位可以表示1~2w%k-1，例：w=14，k=3，2w%k-1=3，即可以表示1,2,3，故非完整部分的答案为：
for(i→2w%k-1) tot+=c[2k-1-w/k-i+1];
最后，最终答案为残位方案与完位方案之和，即ans+tot；
代码如下：
int c[maxn][201],ans[210],y,z,k,w
void Plus(int [],int [],int []); ;高精加数组，最高二百位，故第二维略大于200即可
void Dealone(); No.1处理完整的2^k进制的个数
void Dealtwo(); No.2 处理不完整的方案
void Init(){
scanf("%d%d",&k,&w);
ans[0]=1;
y=pow(2,k)-1; 假设可使用的数是1、2、3、……y，比较方便
for(int i=1;i<=y;i++){ c[i][1]=i; c[i][0]=1;}只有一位的数的初始化__i种
z=w/k; z:表示完整的2^k进制的个数
如k3即8进制，w=7，7/k=7/3=2 ，即可以组成两个完整的8进制： #（&&&） （&&&）
z=min(z,y); 当题目所给的w过大导致z超过了2^k进制升序最大位数
如k=3即8进制满足题意的最大数为1234567最大有7个8进制位，当w给100000000时这里就需要取小，即最多可以组成7个完整的八进制位
Dealone(); No.1处理完整的2^k进制的个数
Dealtwo(); No.2 处理不完整的方案
for(int i=ans[0];i>0;i--)printf("%d",ans[i]);
}
void Dealone(){
for(int i=2;i<=z;i++){ 题目要求至少两位 ，从2开始
for(int j=1;j<=y-i+1;j++)Plus(c[j],c[j-1],c[j]);
由上表分析可知从c【i】=c【i-1】+未更新的c【i】
为什么j<=y-i+1,答：最高位 是i，后面的数必须比i大，只能使用y-i+i个数
Plus(ans,c[y-i+1],ans);
}
}
void Dealtwo(){
int x=pow(2,w%k)-1; 由上表分析x表示不完整的2^k进制位能表示的数有几个
for(int i=1;i<=x && y-z-i+1>=1;i++)Plus(ans,c[y-z-i+1],ans); 边界很重要
如上表：k=3，w=7不完整的2^k进制可以表示1，当i=1时相当于最高位大于等于2的个数c[5]
}
void Plus(int a[],int b[],int d[]){
int c[210]={0}; d[]数组本来有值，不能直接jia
c[0]=max(a[0],b[0]);
for(int i=1;i<=c[0];i++){
c[i]+=a[i]+b[i];c[i+1]+=c[i]/10;c[i]%=10;
}
if(c[c[0]+1]!=0)c[0]++;
for(int i=0;i<=c[0];i++)d[i]=c[i];
}
复杂度分析：
首先，由于高精度数的位数不会太多，故把高精加的效率看成是常数。
代码中dealone外层共进行w/k-1次，内层共进行2k-1次，故dealone的时间复杂度为O(w/k*2k)。
Dealtwo只有一层且最多进行2k次，故dealtwo的时间复杂度为O(2k)。
故总时间复杂度为O((w/k+1)*2k)，消去常数得复杂度为O(2kw/k)。
由于k很小，可以认为k和2k均为常数，故总的时间复杂度为O(w)。
显然空间复杂度为O(w)。
*/
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=30100;
int c[maxn][201],ans[210],y,z,k,w;;//高精加的准备数组，最高二百位，故第二位略大于200即可
void Plus(int [],int [],int []);//数较大，高精加
void Dealone();
void Dealtwo();
void Init();
int main(){
freopen("digital.in","r",stdin);
freopen("digital.out","w",stdout);
Init();
return 0;
}
void Init(){
scanf("%d%d",&k,&w);
ans[0]=1;
y=pow(2,k)-1;//假设可使用的数是1、2、3、……y，比较方便
for(int i=1;i<=y;i++){
c[i][1]=i;//只有一位的数的初始化--i种
c[i][0]=1;
}
z=w/k;//z:可表示完整的2^k进制的个数
//如k3即8进制，w=7，7/k=7/3=2 ，即可以组成两个完整的8进制（括号中的）： # （&&&） （&&&）
z=min(z,y);//当题目所给的w过大导致z超过了2^k进制升序最大位数
//（如k=3即8进制满足题意的最大数为1234567最大有7个8进制位，当w给100000000时这里就需要取小，即最多可以组成7个完整的八进制位）
Dealone();//No.1处理完整的2^k进制的个数
Dealtwo();//No.2 处理不完整的方案
for(int i=ans[0];i>0;i--){//倒序输出
printf("%d",ans[i]);
}
}
void Dealone(){
for(int i=2;i<=z;i++){//题目要求至少两位
for(int j=1;j<=y-i+1;j++){
Plus(c[j],c[j-1],c[j]);
}
//由分析可知从c【i】=c【i-1】+未更新的c【i】
//不懂请看下表，you may mingbai....
//important！！为什么j<=y-i+1,答：最高位 是i，后面的数必须比i大，只能使用y-i+i个数
Plus(ans,c[y-i+1],ans);
//答案加上i位数的方案数，显然还要用高精
}
}
void Dealtwo(){
int x=pow(2,w%k)-1;
//x表示不完整的2^k进制位能表示的数有几个
//（如k=3即8进制，w=7 0 000 000不完整的8进制位只能表示1）
for(int i=1;i<=x && y-z-i+1>=1/*边界*/;i++){
Plus(ans,c[y-z-i+1],ans);
//如下表：k=3即8进制，w=7不完整的2^k进制可以表示1，当i=1时相当于最高位大于等于2的个数即c[5]
}
}
void Plus(int a[],int b[],int d[]){
int c[210]={0};//d[]数组本来有值，不能直接jia
c[0]=max(a[0],b[0]);
for(int i=1;i<=c[0];i++){
c[i]+=a[i]+b[i];
c[i+1]+=c[i]/10;
c[i]%=10;
}
if(c[c[0]+1]!=0)c[0]++;
for(int i=0;i<=c[0];i++)d[i]=c[i];
}