题目地址：洛谷：【P1066】2^k进制数 – 洛谷

题目描述

设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”组成），S对应于上述条件3中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2^k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2^k 进制数r。
例：设k=3，w=7。则r是个八进制数（2^3=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：

3 7

输出样例#1：

36

说明

NOIP 2006 提高组 第四题

题解

锻炼一下高精。
首先可以很快得到一个DP方程，用dp[i][j]表示最高位为第i位且该位填j的方案数，有dp[1][1~2^k-1]=1，方程如下
dp[i][j] = \sum_{j'=j+1}^{2^k-1} dp[i-1][j']
而答案是 \displaystyle \sum_{i=2}^{\lceil \frac{W}{k} \rceil} \sum_{j=1, k(i-1)+\log_2 j \leq W}^{2^k-1} dp[i][j] ，注意到最高位以后要特判一下超没超W。
然后套个烦人的压位高精板子。有点卡常，最好卡着开空间，加上一个滚动数组。空间开太大memset会TLE。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstring>

inline int max(int a, int b) {
    return a > b ? a : b;
}

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005;

const int BMO = 1e9;

struct Bint {
    int len, num[30];
    inline Bint& operator=(const int &rhs) {
        num[0] += rhs;
        for(register int i = 0; i <= len; i++) {
            if(num[i] < BMO) break;
            num[i + 1]++;
            num[i] -= BMO;
            if(i == len) len++;
        }
        return *this;
    }
    inline Bint operator+(const Bint &rhs) const {
        Bint res = *this;
        res.len = max(res.len, rhs.len);
        for(register int i = 0; i <= res.len; i++) {
            res.num[i] += rhs.num[i];
            if(res.num[i] < BMO) continue;
            res.num[i + 1]++;
            res.num[i] -= BMO;
            if(i == res.len) res.len++;
        }
        return res;
    }
    inline Bint& operator+=(const Bint &x) {
        return *this = *this + x;
    }
    inline void print() {
        for(register int i = len; i >= 0; i--) {
            if(i == len) printf("%d", num[i]);
            else printf("%09d", num[i]);
        }
    }
};

int k, w, len[1 << 9];
Bint ans, dp[2][1 << 9];

int main() {
    k = readint(); w = readint();
    for(register int i = 1; i < 1 << k; i++) {
        dp[1][i] = 1;
    }
    for(register int i = 1; i < 1 << k; i++) {
        len[i] = len[i >> 1] + 1;
    }
    int lim = ceil(double(w) / k);
    for(register int i = 2; i <= lim; i++) {
        memset(dp[i & 1], 0, sizeof(dp[i & 1]));
        for(int j = 1; j < 1 << k; j++) {
            for(int jj = j + 1; jj < 1 << k; jj++) {
                dp[i & 1][j] += dp[i & 1 ^ 1][jj];
            }
            if((i - 1) * k + len[j] <= w) ans += dp[i & 1][j];
            else break;
        }
    }
    ans.print();
    return 0;
}