题目相关

题目链接: 洛谷 P1066 [NOIP 2006 提高组] 2^k进制数

题目描述

设 $r$ 是个 $2^k$ 进制数，并满足以下条件：

$r$ 至少是个 $2$ 位的 $2^k$ 进制数。
作为 $2^k$ 进制数，除最后一位外，$r$ 的每一位严格小于它右边相邻的那一位。
将 $r$ 转换为二进制数 $q$ 后，则 $q$ 的总位数不超过 $w$。

在这里，正整数 $k,w$ 是事先给定的。

问：满足上述条件的不同的 $r$ 共有多少个？

我们再从另一角度作些解释：设 $S$ 是长度为 $w$ 的 $01$ 字符串（即字符串 $S$ 由 $w$ 个 $0$ 或 $1$ 组成），$S$ 对应于上述条件三中的 $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$ 个。

输入格式

一行两个正整数 $k,w$ 用一个空格隔开：

输出格式

一行一个个正整数，为所求的计算结果。
即满足条件的不同的 $r$ 的个数（用十进制数表示），要求不得有前导零，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。

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

样例 #1

样例输入 #1

3 7

样例输出 #1

提示

【数据范围】
$1\le k \le 9$
$1\le w \le 3\times 10^4$

NOIP 2006 提高组第四题

题目解析

题目可能较为难以理解，但可以参考原题目的解释。

一个数可以被分为两部分：前导 $0$ 部分和数值部分。

对于数值部分，要求其每一位是单调不降的。每一位的情况可以是 $[1,2^k-1]$ 一共 $2^k-1$ 种（数值部分任何一位不为 $0$，因为最高（左）位为 $1$（否则将会归于前导 $0$ 部分），而右侧位数字不会小于左侧位），对于要求严格单调递增的数列，可以理解为从所有情况中选取不同的数组成唯一方案。
对于这里，如果位数为 $b$，那么可行的方案便有 $C_{2^k-1}^{b}$ 种。

对于存在前导 $0$ 的数据，其位数最多为 $\lfloor \frac{w-1}{k} \rfloor$，那么该部分结果为 $\sum\limits_{b=2}^{\lfloor \frac{w-1}{k} \rfloor} C_{2^k-1}^{b}$ 种。

对于没有前导 $0$ 的数据，其首位 $f$ 可取的值为 $[1,2^{w-k\cdot \lfloor \frac{w-1}{k} \rfloor}-1]$，对于其他位，可选的范围为 $[f+1,2^k-1]$ 共 $2^k-(f+1)$，该部分结果为 $\sum\limits_{f=1}^{2^{w-k\cdot \lfloor \frac{w-1}{k} \rfloor} - 1}C_{2^k-(f+1)}^{\lfloor \frac{w-1}{k} \rfloor}$。

将两部分相加即可得到最终结果。由于结果很大，需要使用高精度存储。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

// BigInt start
const int BIGINT_MAX_NUM = 9999;
const int BIGINT_BIT_LEN = 4;
const int BIGINT_MAX_BIT = 55;
struct BigInt {
    int len, data[BIGINT_MAX_BIT];
    BigInt() {
        len = 1;
        memset(data, 0, sizeof(data));
    }
    BigInt(const int &x) {
        len = 0;
        memset(data, 0, sizeof(data));
        int c, d = x;
        while (d > BIGINT_MAX_NUM) {
            c = d - d / (BIGINT_MAX_NUM + 1) * (BIGINT_MAX_NUM + 1);
            d = d / (BIGINT_MAX_NUM + 1);
            data[len++] = c;
        }
        data[len++] = d;
    }
};
BigInt operator+(const BigInt &a, const BigInt &b) {
    BigInt result(0);
    result.len = max(a.len, b.len);
    for (int i = 0; i < result.len; ++i) {
        result.data[i] = result.data[i] + a.data[i] + b.data[i];
        if (result.data[i] > BIGINT_MAX_NUM) {
            ++result.data[i + 1];
            result.data[i] -= BIGINT_MAX_NUM + 1;
        }
    }
    if (result.data[result.len]) ++result.len;
    return result;
}
void printBigInt(const BigInt &x) {
    printf("%d", x.data[x.len - 1]);
    for (int i = x.len - 2; i >= 0; --i) {
        printf("%04d", x.data[i]);
    }
}
// BigInt end

const int MAXK = 9;
const int MAXW = 3e4 + 10;
const int MAXC = (1 << MAXK) + 5;
int k, w;
BigInt C[MAXC][MAXC];
BigInt ans;

int main() {
    scanf("%d%d", &k, &w);

    // compute C
    int n = (1 << k) - 1;  // max value in C
    C[1][0] = BigInt(1);
    C[1][1] = BigInt(1);
    for (int i = 2; i <= n; ++i) {
        C[i][0] = BigInt(1);
        for (int j = 1; j <= i; ++j) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }

    // calculate ans
    BigInt ans;
    for (int b = 2; b <= (w - 1) / k; ++b) {
        if ((1 << k) - 1 < b) break;
        ans = ans + C[(1 << k) - 1][b];
    }
    for (int f = 1; f < (1 << (w - (w - 1) / k * k)); ++f) {
        if ((1 << k) - (f + 1) < (w - 1) / k) break;
        ans = ans + C[(1 << k) - (f + 1)][(w - 1) / k];
    }

    printBigInt(ans);
    return 0;
}