在 C++ 中计算长度为 N 且仅包含 0 和 1 的二进制字符串的数量
c++server side programmingprogramming更新于 2024/9/27 5:20:00
给定一个数字，假设为 num，任务是计算通过给定数字 num 可以形成的仅包含 o 和 1 的二进制字符串的数量。
二进制数系统是数字表示技术的一种。它在数字系统中最为流行和使用。二进制系统用于表示二进制数量，任何只有两种操作状态或可能条件的设备都可以表示二进制数量。例如，开关只有两种状态:打开或关闭。
在二进制系统中，只有两个符号或可能的数字值，即 0 和 1。由任何只有 2 种操作状态或可能条件的设备表示。二进制字符串是包含二进制值(即 0 或 1)的字符串。
例如
输入 − num = 3 输出 − 计数为 8
解释 长度为 3 的 − 二进制组合有:000、111、001、101、100、110、011、010，因为它们总共有 8 个，所以计数为 8。
输入 − num = 2 输出 − 计数为 4
解释 −长度为 2 的二进制组合有:00、11、01、10，因为它们总共有 4 个数字，因此计数为 4。
以下程序中使用的方法如下
输入一个 long long 类型的数字，因为该数字可以是任何数字 long
计算 mod 值为 (long long)(le9 + 7)
创建一个函数来计算计数
声明一个临时变量来存储计数和另一个变量 temp，并用 2 初始化它。
将 num 设置为 temp = temp % mod
当 num > 0 时启动循环
检查 num & 1 然后将 count 设置为 (count * temp)% mod
设置 num = num >> 1
设置 temp = (temp * temp) % mod
返回 count
打印结果。
示例
#include <iostream>
using namespace std;
#define ll long long
#define mod (ll)(1e9 + 7)
// 一个迭代函数，用于在 O(log y) 中查找 (x^y)%p
ll power(ll x, ll y, ll p){
ll result = 1;
x = x % p; // 如果 x 大于或等于 p，则更新 x
// 等于 p
while (y > 0){
// 如果 y 为奇数，则将 x 与结果相乘
if (y & 1){
result = (result * x) % p;
}
// y 现在必须是偶数
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return result;
}
// 计算二进制字符串数量的函数
ll countbstring(ll num){
int count = power(2, num, mod);
return count;
}
int main(){
ll num = 3;
cout <<"count is: "<<countbstring(num);
return 0;
}
输出
如果运行上述代码，我们将得到以下输出 −
计数为:8
