易变数
们定义以下正整数变形操作。
对于一个正整数 x，如果其二进制表示恰好包含 y 个 1，那么经过一次变形操作后，x将变为 y。
例如，对于正整数13，其二进制表示为 1101，其中恰好包含 3 个 1，所以 13 经过一次变形操作后会变为 3。
如果一个正整数通过上述变形操作变为 1 所需要的最少操作次数恰好为 k，那么就称这个数是一个易变数。
给定一个正整数 n 的不含前导 0 的二进制表示，请你计算 [1,n] 范围内的易变数的数量。
由于结果可能很大，你只需要输出对 1e9 + 7 取模后的结果。
输入样例
输出
这道题花了挺长时间的，主要原因是因为对数位DP的不熟练和这道题有点坑。
这道题的数位DP不存在跳位而且前导零不影响结果,因此不需要isNum，剩下这个题就比较容易写出来了,这题比较坑的点还有就是当k为0和n为1时都需要特判，有点搞心态。
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
| long mod = (long) (1e9 + 7);
String s = in.next();
int k = in.nextInt();
Long[][] cache = new Long[1005][1005];
HashSet<Integer> set = new HashSet<>();
void solve() {
out.println(s.length());
if (k == 0) {
out.println(1);
return;
} else {
for (int i = 1; i <= s.length(); i++) {
if (check(i)) set.add(i);
}
}
out.println(dfs(true, 0, 0) - (k == 1 ? 1 : 0));
}
long dfs(boolean isLimit, int i, int cnt) {
if (i == s.length()) {
return set.contains(cnt) ? 1 : 0;
}
if (!isLimit && cache[i][cnt] != null) return cache[i][cnt];
long res = 0L;
int lo = 0;
int up = isLimit ? (s.charAt(i) - '0') : 1;
for (int j = lo; j <= up; j++) {
res = (res + dfs(isLimit && j == up, i + 1, cnt + (j == 1 ? 1 : 0))) % mod;
}
if (!isLimit) cache[i][cnt] = res;
return res;
}
boolean check(int x) {
int c = 1;
while (x != 1) {
x = Integer.bitCount(x);
c++;
}
return c == k;
}
|