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+\dots +1=21$ 个。

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

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

输入格式

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

输出格式

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

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

样例 #1

样例输入 #1

3 7

样例输出 #1

36

提示

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

题目来源

NOIP 2006 提高组 第四题（洛谷）

题解

#include<bits/stdc++.h>
using namespace std;// 比较两个高精度数a和b，a >= b返回1，否则返回0
inline bool comp(string a, string b) {if (a.size() < b.size())return 0;if (a.size() > b.size())return 1;for (int i = a.size() - 1; i >= 0; i--) {if (a[i] < b[i])return 0;if (a[i] > b[i])return 1;}return 1;
}// 求两个高精度数a和b的和
inline string sum(string a, string b) {if (comp(a, b) == 0)swap(a, b);string c = "";char x[2] = "";bool n = 0;int bpt = b.size() - 1;for (int i = a.size() - 1; i >= 0; i--) {if (b[bpt] < '0' || b[bpt] > '9')b[bpt] = '0';x[0] = a[i] + b[bpt] - '0';if (n == 1) {x[0]++;n = 0;}if (x[0] > '9') {x[0] -= 10;n = 1;}c.insert(0, x);bpt--;if (bpt < 0) {bpt = 0;b[0] = '0';}}if (n == 1)c.insert(0, "1");while (c[0] == '0')c.erase(0, 1);if (c.size() == 0)c.insert(0, "0");return c;
}// 求两个高精度数a和b的差（保证结果为正数）
string dif(string a, string b) {string c = "";char x[2] = "";bool n = 0;int bpt = b.size() - 1;for (int i = a.size() - 1; i >= 0; i--) {if (b[bpt] < '0' || b[bpt] > '9')b[bpt] = '0';x[0] = a[i] - b[bpt] + '0';if (n == 1) {x[0]--;n = 0;}if (x[0] < '0') {x[0] += 10;n = 1;}c.insert(0, x);bpt--;if (bpt < 0) {bpt = 0;b[0] = '0';}}while (c[0] == '0')c.erase(0, 1);if (c.size() == 0)c.insert(0, "0");return c;
}// 求高精度数a与整型数b的积
string mul(string a, int b) {string c = "";char x[2] = "";int n = 0, y;for (int i = a.size() - 1; i >= 0; i--) {y = 0;if (n > 0)y = n;n = (a[i] - '0') * b + y;x[0] = n % 10 + '0';n /= 10;if (x[0] > '9') {x[0] -= 10;n++;}c.insert(0, x);}while (n > 0) {x[0] = n % 10 + '0';n /= 10;c.insert(0, x);}while (c[0] == '0')c.erase(0, 1);if (c.size() == 0)c.insert(0, "0");return c;
}// 求高精度数a与整型数b的商
string div(string a, int b) {string c = "";char x[2] = "";int n = 0, y;for (int i = 0; i < a.size(); i++) {n *= 10;n += a[i] - '0';x[0] = n / b + '0';n %= b;c.insert(c.size(), x);}while (n > 0) {x[0] = n % 10 + '0';n /= 10;c.insert(0, x);}while (c[0] == '0')c.erase(0, 1);if (c.size() == 0)c.insert(0, "0");return c;
}// 把整型数转化成高精度数
string change(int num) {if (num == 0)return "0";string a = "";char c[2] = "";while (num > 0) {c[0] = num % 10 + '0';num /= 10;a.insert(0, c);}return a;
}// 覆盖（即用一个高精度数覆盖另一个高精度数）
void instead(string &s, string s0) {s.erase(0, s.size());s.insert(0, s0);
}string c[50000];
const int power[10] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 }; // 打表计算2^nint main() {int k, w;cin >> k >> w;// 计算符合条件的两位数的数量c[2] = change((power[k] - 1) * (power[k] - 2) / 2);string ans = c[2];int most = min(w / k + (w % k == 0 ? 0 : 1), power[k] - 1); // most存储max（max不能定义）for (int i = 3; i <= most; i++) {if ((power[k] - i) % i == 0)c[i].insert(0, mul(c[i - 1], (power[k] - i) / i));elsec[i].insert(0, div(mul(c[i - 1], power[k] - i), i));ans = sum(ans, c[i]);}instead(c[most - 1], "1");int most2 = min(power[w % k] - 1, power[k] - most - 1);if (power[k] - most <= power[w % k] - 1 || most2 <= 0) {cout << ans;return 0;}// 特殊情况，如3 17，最大234567，上限6位3起，这时会误判ans = dif(ans, "1"); // 首位为max-1时要减掉for (int i = most; i < power[k] - 1 - most2; i++) {if (i % (i - most + 1) == 0)instead(c[i], mul(c[i - 1], i / (i - most + 1)));elseinstead(c[i], div(mul(c[i - 1], i), i - most + 1));ans = dif(ans, c[i]);}cout << ans;
}