题解 | #牛妹的位运算#
牛妹的位运算
https://www.nowcoder.com/practice/7f131dd26f4043839d0342ed6f65ddf3
题目链接
题目描述
给定一个正整数 ，要求在区间
内寻找满足以下所有条件的非负整数对
的数量：
结果需要对 取模。
解题思路
这是一个位运算相关的计数问题。核心在于理解并简化条件 。
条件转换
让我们从二进制表示的角度来分析这个不等式。
设 ，
。为了比较
和
的大小，我们通常从它们的最高位开始比较。
设 是
或
中最高有效位（Most Significant Bit, MSB）的位置。也就是说，
是使得
的第
位或
的第
位为 1 的最大下标。对于所有
，
和
的第
位都为 0。
- 对于所有
，
和
的第
位显然也都是 0。
- 现在考虑第
位：
- 因为
和
在第
- 情况 1：
。
。
- 在这种情况下，
。
- 情况 2：
。
。
- 在这种情况下，
。
- 因为
由此我们得出结论：不等式 成立，当且仅当在
和
的最高公共有效位
上，它们的值不相同。这等价于说，
和
的最高有效位在不同的位置上。
为方便起见，我们定义
为
的最高有效位的索引（例如
），并定义
。
那么，原条件就等价于
。
组合计数
现在问题转化为：计算满足 且
的数对
的数量。
我们可以分情况讨论：
-
当
时：
。条件变为
，这意味着
，所以
恒成立。 因此，
内的任何整数。 这种情况下的数对数量为
。
-
当
时： 设
，
。 条件
。 条件
意味着
。 结合两者，我们必须有
。
我们对
和
取到
。
- 对于每个固定的
取到
。
对于固定的
- 满足
的
(即从
)。
- 满足
的
(即从
)。
- 因为
的
的
- 因此，对于固定的
，有
对
。
总数量为
。 内部的和是等比数列求和：
。 所以，和式变为
。 再次使用等比数列求和公式：
这部分的数量为
。
合并结果
总数 = (情况1的数量) + (情况2的数量)
。
我们只需要计算 即可。这需要用到快速幂和模逆元。
代码
#include <iostream>
using namespace std;
long long power(long long base, long long exp) {
long long res = 1;
base %= 1000000007;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % 1000000007;
base = (base * base) % 1000000007;
exp /= 2;
}
return res;
}
long long modInverse(long long n) {
return power(n, 1000000007 - 2);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k;
cin >> k;
long long p4k = power(4, k);
long long numerator = (p4k - 1 + 1000000007) % 1000000007;
long long inv3 = modInverse(3);
long long ans = (numerator * inv3) % 1000000007;
cout << ans << endl;
return 0;
}
import java.util.Scanner;
public class Main {
static long power(long base, long exp) {
long res = 1;
long mod = 1000000007;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return res;
}
static long modInverse(long n) {
long mod = 1000000007;
return power(n, mod - 2);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
long mod = 1000000007;
long p4k = power(4, k);
long numerator = (p4k - 1 + mod) % mod;
long inv3 = modInverse(3);
long ans = (numerator * inv3) % mod;
System.out.println(ans);
}
}
def power(base, exp):
res = 1
mod = 10**9 + 7
base %= mod
while exp > 0:
if exp % 2 == 1:
res = (res * base) % mod
base = (base * base) % mod
exp //= 2
return res
def mod_inverse(n):
mod = 10**9 + 7
return power(n, mod - 2)
def solve():
k = int(input())
mod = 10**9 + 7
p4k = power(4, k)
numerator = (p4k - 1 + mod) % mod
inv3 = mod_inverse(3)
ans = (numerator * inv3) % mod
print(ans)
solve()
算法及复杂度
- 算法：数学 + 组合计数 + 模运算。通过分析位运算性质将问题转化为计数问题，并通过推导数学公式得到封闭解。
- 时间复杂度：计算结果主要依赖于快速幂运算，其时间复杂度为
。
- 空间复杂度：算法只需要常数个变量，空间复杂度为
。
查看7道真题和解析
