为什么老师没有放 06 年的T4，害得我都不能直接(超)借鉴思路了（bushi）

T4 2^k进制数

组合数学 + 计数

solution

显然地，一个 $n$ 位的 $2^k$ 进制数转化为 $2$ 进制数后有 $kn$ 位，所以有：

$$\begin{split} kn &\leq w \\ \therefore n &\leq \lceil \frac wk \rceil \end{split}$$

其中最高位可能不满 $k$ 位，当 $w \equiv 0 \pmod k$ 时最高位是 $k$ 位

首先当最高位为 $0$ 时，由题目所求的数 $r$ 至少有 $2$ 位，且每一位严格小于它右边相邻的那一位。所以当我们有 $p$ 位且不为 $0$ 时，每一位有 $[1 , 2^k - 1]$ 种可能，所以答案可以转变为从 $2^k - 1$ 个数中选 $p$ 个数的组合

因为 $r$ 可能有 $2$ 位，$3$ 位 ... $n - 1$ 位，所以把可能加起来，为：

$$cnt = \sum_{i = 2}^{\lfloor \frac wk \rfloor}{\binom{2^k - 1}{i}}$$

注意当最高位为 $k$ 位时不用分类讨论，直接就是这个结果（可以自己想一想为什么）

当最高位不为 $0$ 时，最高位转化为 $2$ 进制数后有 $w \bmod k$ 位，所以最高位有 $[1 , 2^{w \bmod k} - 1]$ 种取值，最高位后面每一位有 $[g + 1 , 2 ^ k - 1]$ 种取值（$1 \leq g \leq 2^{w \bmod k} - 1$）

一共有 $\lfloor \frac wk \rfloor$ 位，所以枚举最高位的取值，把可能加起来有：

$$\begin{split} cnt' &= \sum_{i = 1}^{2^{w \bmod k} - 1}{\binom{2^k - i - 1}{\lfloor \frac wk \rfloor}} \\ \therefore ans &= \sum_{i = 2}^{\lfloor \frac wk \rfloor}{\binom{2^k - 1}{i}} + \sum_{i = 1}^{2^{w \bmod k} - 1}{\binom{2^k - i - 1}{\lfloor \frac wk \rfloor}} \end{split}$$

递推预处理组合数，再暴力加即可，组合数范围最多 $2^k - 1 \leq 512$，注意用高精度处理（最烦人）

code

#include<bits/stdc++.h>
using namespace std;

const int N = 520;

struct hp {
	int a[205] = {0}, len = 0;

	hp operator =(string s) {
		len = s.length() - 1;
		for (int i = 0 ; i <= len ; i ++) a[i] = s[len - i] - '0';
		return *this;
	}
	hp operator +(hp b) {
		hp ans;
		ans.len = max(len, b.len);
		for (int i = 0 ; i <= ans.len ; i ++) {
			ans.a[i] += a[i] + b.a[i];
			ans.a[i + 1] += ans.a[i] / 10;
			ans.a[i] %= 10;
		}
		if (ans.a[ans.len] > 0) ans.len ++;
		return ans;
	}
};

bool cmp(const hp &a, const hp &b) {
	for (int i = max(a.len, b.len) ; i >= 0 ; i --) {
		if (a.a[i] > b.a[i]) return true;
		if (a.a[i] < b.a[i]) return false;
	}
	return true;
}

void print(hp ans) {
	for (int i = ans.len - 1 ; i >= 0 ; i --) cout << ans.a[i];
}

int w, k;
hp c[N][N] , ans , a , b;

int main() {
	cin >> k >> w;
	
	int t = (1 << k);
	c[0][0] = "1";
	for(int i = 1 ; i < t ; i ++){
		c[i][0] = c[i][i] = "1";
	}
	for(int i = 1 ; i < t ; i ++){
		for(int j = 1 ; j < i ; j ++){
			c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
		}
	}
	
	ans = "0";
	for(int i = 2 ; i <= w / k ; i ++){
		if(i > t - 1) break;
		ans = ans + c[t - 1][i];
	}
	int s = w / k , r = (1 << (w % k));
	for(int i = 1 ; i <= r - 1 ; i ++){
		if(s > t - 1 - i) break;
		ans = ans + c[t - 1 - i][s];
	}
	print(ans);
	return 0;
}