2^k进制数 vijos1315 NOIP2006提高组T4

时间：2022-12-16 13:45:50

 

题面在最下方。

从题意中可以获取灵感：k与w是有关系的。

当这个2^k进制数转化为2进制时，原来的每一位（可以相对于十进制中的每一位来理解）都对应了二进制数中长为k的一个区段。

举个栗子，对于一个16（2^4）进制的数 ABCD （即 10 11 12 13）

打开windows自带的计算器就能看到：2^k进制数 vijos1315 NOIP2006提高组T4，其中 A对应二进制下的1010，B对应1011，以此类推。

所以这就体现出了阶段性的特点，可以考虑采用DP解答。 

首先要做的准备工作：

根据题意“在2^k进制下的这个数的位数要大于等于2，数字严格上升”，所以不可能有任何有效位取0的情况(可以有前导零)。

设当前推导位（第i位）取值范围为[1,maxx]，令x=w%n，对于maxx讨论如下：

若 x==0 ， 则所有位的取值范围都是[1,(1<<k)-1]。

若 x!=0 ，则在最高位上可取的值为 [1,(1<<x)-1]，其他位是[1,(1<<k)-1]。

从低位向高位推导，令 F[i][j] 是第i位上放数字j后满足条件的总方案数

则转移方程为 F[i][j]=∑F[i-1][k](j<k<=maxx)

同时由于w限制的是最大位数而非必需位数，所以在每次转移过后，都要 ans+=F[i][j]

 

如何优化？

第一个简单的优化，每一次状态转移的求和可以用后缀数组进行优化。

第二个优化是可以用滚动数组的思想，把F[i][j]优化为一维的F[i]，具体可看代码实现。

其他要说的

高精度的模版是我从网上扒下来的，至今不会写高精度（逃）

 

2^k进制数 vijos1315 NOIP2006提高组T42^k进制数 vijos1315 NOIP2006提高组T4
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<string>
  5 using namespace std;
  6 template<class T> inline void read(T &_a){
  7     bool f=0;int _ch=getchar();_a=0;
  8     while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
  9     while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
 10     if(f)_a=-_a;
 11 }
 12 const int maxn = 300;    
 13     
 14 struct bign{    
 15     int d[maxn], len;    
 16     void clean() { while(len > 1 && !d[len-1]) len--; }    
 17     
 18     bign()    { memset(d, 0, sizeof(d)); len = 1; }    
 19     bign(int num)     { *this = num; }     
 20     bign(char* num) { *this = num; }    
 21     bign operator = (const char* num){    
 22     memset(d, 0, sizeof(d)); len = strlen(num);    
 23     for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';    
 24     clean();    
 25     return *this;    
 26     }    
 27     bign operator = (int num){    
 28     char s[20]; sprintf(s, "%d", num);    
 29     *this = s;    
 30     return *this;    
 31     }    
 32     
 33     bign operator + (const bign& b){    
 34     bign c = *this; int i;    
 35     for (i = 0; i < b.len; i++){    
 36     c.d[i] += b.d[i];    
 37     if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;    
 38     }    
 39     while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;    
 40     c.len = max(len, b.len);    
 41     if (c.d[i] && c.len <= i) c.len = i+1;    
 42     return c;    
 43     }    
 44     bign operator - (const bign& b){    
 45     bign c = *this; int i;    
 46     for (i = 0; i < b.len; i++){    
 47     c.d[i] -= b.d[i];    
 48     if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;    
 49     }    
 50     while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;    
 51     c.clean();    
 52     return c;    
 53     }    
 54     bign operator * (const bign& b)const{    
 55     int i, j; bign c; c.len = len + b.len;     
 56     for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)     
 57     c.d[i+j] += d[i] * b.d[j];    
 58     for(i = 0; i < c.len-1; i++)    
 59     c.d[i+1] += c.d[i]/10, c.d[i] %= 10;    
 60     c.clean();    
 61     return c;    
 62     }    
 63     bign operator / (const bign& b){    
 64     int i, j;    
 65     bign c = *this, a = 0;    
 66     for (i = len - 1; i >= 0; i--)    
 67     {    
 68     a = a*10 + d[i];    
 69     for (j = 0; j < 10; j++) if (a < b*(j+1)) break;    
 70     c.d[i] = j;    
 71     a = a - b*j;    
 72     }    
 73     c.clean();    
 74     return c;    
 75     }    
 76     bign operator % (const bign& b){    
 77     int i, j;    
 78     bign a = 0;    
 79     for (i = len - 1; i >= 0; i--)    
 80     {    
 81     a = a*10 + d[i];    
 82     for (j = 0; j < 10; j++) if (a < b*(j+1)) break;    
 83     a = a - b*j;    
 84     }    
 85     return a;    
 86     }    
 87     bign operator += (const bign& b){    
 88     *this = *this + b;    
 89     return *this;    
 90     }    
 91     
 92     bool operator <(const bign& b) const{    
 93     if(len != b.len) return len < b.len;    
 94     for(int i = len-1; i >= 0; i--)    
 95     if(d[i] != b.d[i]) return d[i] < b.d[i];    
 96     return false;    
 97     }    
 98     bool operator >(const bign& b) const{return b < *this;}    
 99     bool operator<=(const bign& b) const{return !(b < *this);}    
100     bool operator>=(const bign& b) const{return !(*this < b);}    
101     bool operator!=(const bign& b) const{return b < *this || *this < b;}    
102     bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}    
103     
104     string str() const{    
105     char s[maxn]={};    
106     for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';    
107     return s;    
108     }    
109 };
110 
111 int k,w,deg,maxx;
112 bign f[1<<10],sum[1<<10],ans;
113 
114 int main()
115 {
116     read(k); read(w);
117     deg=(1<<k)-1;
118     for (register int i=0;i<=deg;++i) f[i]=1;
119     while(w>=k)
120     {
121         w-=k;
122         if(w>=k) maxx=deg;
123             else maxx=(1<<w)-1;
124         for (register int i=deg;i;--i) sum[i]=sum[i+1]+f[i];
125         for (register int i=1;i<=maxx;++i) f[i]=sum[i+1],ans+=f[i];
126     }
127     printf("%s",ans.str().begin());
128     return 0;
129 }
View Code

 

 

描述

设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）是事先给定的。

问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”m组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2^k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2^k 进制数r。

例：设k=3，w=7。则r是个八进制数（23=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：
2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。

3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。

所以，满足要求的r共有36个。

格式

输入格式

输入文件只有1行，为两个正整数，用一个空格隔开：
k W

输出格式

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

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

样例1

样例输入1

3 7

样例输出1

36

限制

1s

标签：

相关文章