题面在最下方。

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

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

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

打开windows自带的计算器就能看到：，其中 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]，具体可看代码实现。

其他要说的

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

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 template
          
            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)120 {121 w-=k;122 if(w>=k) maxx=deg;123 else maxx=(1<
           
          
         
        
       
      

 

 

描述

设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