C. Travelling Salesman and Special Numbers (二进制 + 组合数)

C. Travelling Salesman and Special Numbers

题意
给定一个数 n，问 1 - n 中一共有多少数能够经过 m 次下面的转换变为 1？

• 对于一个数 x，如果其对应二进制一共有 k 位为 1，那么 x 变为 k。

$(1\le n<2^{1000},0\le m\le 1000)$
$n给出无前导零的二进制。$

思路
虽然 n 很大，但是再大的数执行一次转换之后都小于 1000 了。
假设执行过一次操作变为 x，x 经过 k 次操作变为了1，那么 n 就要执行 k+1 次操作变为1。
所以可以先暴力求出 1-1000 中所有数分别需要多少次转换变为1，假设一个数 x 经过 k 次操作变为1，那么如果一个数经过 k+1 次操作变为1，其二进制中1的个数就为 x。
对于每个操作次数 k，提前存储其对应的原数二进制表达中 1 的个数。
例如：如果操作次数为 2，那么原数二进制有就应该有 2 或 4 或 8 或 16 … 个 1。

现在给定了 操作次数为 m，我们需要根据给出的 n 的二进制表达找到 1-n 中一共有多少数满足其二进制有 v[0], v[1], v[2]… 个 1。

对于 n 的二进制每一位 1 来说，如果这一位 1 变为 0 了，那么修改过的数无论后面所有位是 0 是 1，都比原来的 n 小。假设前面位置一共有 cnt 个1，后面还有 left 个位置，那么就可以从后面的所有位置中选取 v[i] - cnt 个 和 cnt 组成一共 v[i] 个1。

遍历所有 1 的位置，对于每个位置都遍历需要的 1 的个数，求组合数累加。

int cnt = 0;
for(int i=1;i<=n;i++)
{
	if(a[i] != '1') continue;
	
	for(int x : vv)
	{
		int left = n - i;
		if(cnt > x) continue;
		if(left < x-cnt) continue;
		ans = (ans + C[left][x-cnt]) % mod;
	}
	cnt ++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

需要注意的细节：

• 上面是判断的 1~n-1 的数，n 本身的 1 的个数还要判断是否是需要满足的 1 的个数，如果是，ans ++；
• 当操作数为 1 时，需要满足二进制中有 1 个 1，但是如果这个数是 1 的话，其操作数应该为 0，需要删掉原数为 1 的情况；
• 当操作数为 0 时，原数为 1，n ≥1 一定满足，答案一定为 1。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
char a[N];
vector<int> v[20];
int C[1010][1010];

void init()
{
	for(int i=1;i<1000;i++)
	{
		int x = i;
		int cnt = 0;
		while(x != 1)
		{
			cnt ++;
			bitset<12> f(x);
			x = f.count();
		}
		v[cnt+1].push_back(i);
	}
	
	C[0][0] = 1;
	for(int i=1;i<=1000;i++)
	{
		C[i][0] = 1;
		for(int j=1;j<=i;j++)
		{
			C[i][j] = C[i-1][j-1] + C[i-1][j];
			C[i][j] %= mod;
		}
	}
}

signed main(){
	Ios;
	init();
	
	cin >> a+1;
	n = strlen(a+1);
	
	cin >> m;
	
	if(m > 5){
		cout << 0; return 0;
	}
	if(m == 1 && n == 1){
		cout << 0; return 0;
	}
	if(m == 0){
		cout << 1; return 0;
	}
	
	vector<int> vv = v[m];
	
	int ans = 0;
	if(m == 1) ans --;
	
	int t = 0;
	for(int i=1;i<=n;i++) if(a[i] == '1') t++;
	for(int x : vv) if(x == t) ans ++;
	
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
		if(a[i] != '1') continue;
		
		for(int x : vv)
		{
			int left = n - i;
			if(cnt > x) continue;
			if(left < x-cnt) continue;
			ans = (ans + C[left][x-cnt]) % mod;
		}
		cnt ++;
	}
	cout << ans;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85