เราได้รับตัวเลขหนึ่งตัว ให้เรียกว่า num และงานคือคำนวณจำนวนสตริงไบนารีที่สามารถสร้างได้จากตัวเลข num ที่ประกอบด้วยแค่ 0 และ 1
ระบบเลขฐานสอง (Binary Number System) เป็นหนึ่งในเทคนิคการแทนค่าตัวเลข มันเป็นที่นิยมและใช้ในระบบดิจิทัล ระบบฐานสองใช้แทนปริมาณไบนารีที่สามารถแทนได้โดยอุปกรณ์ใดๆ ที่มีสถานะการทำงานเพียงสองสถานะหรือเงื่อนไขที่เป็นไปได้ ตัวอย่างเช่น สวิตช์มีสองสถานะ: เปิด หรือ ปิด
ในระบบฐานสอง มีเพียงสองสัญลักษณ์หรือค่าตัวเลขที่เป็นไปได้ คือ 0 และ 1 แทนโดยอุปกรณ์ใดๆ ที่มีสถานะการทำงานเพียง 2 สถานะ สตริงไบนารีคือสตริงที่มีค่าไบนารี คือ 0 หรือ 1
ตัวอย่าง
อินพุต – num = 3 เอาต์พุต – count is 8
คำอธิบาย – การจัดหมู่ไบนารีที่สามารถสร้างได้ความยาว 3 คือ: 000, 111, 001, 101, 100, 110, 011, 010 รวมทั้งหมด 8 แบบ ดังนั้น count คือ 8
อินพุต – num = 2 เอาต์พุต – count is 4
คำอธิบาย – การจัดหมู่ไบนารีที่สามารถสร้างได้ความยาว 2 คือ: 00, 11, 01, 10 รวมทั้งหมด 4 แบบ ดังนั้น count คือ 4
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- รับตัวเลขประเภท long long เนื่องจากตัวเลขอาจยาวเท่าไหร่ก็ได้
- คำนวณค่า mod เป็น (long long)(1e9 + 7)
- สร้างฟังก์ชันคำนวณจำนวน
- ประกาศตัวแปรชั่วคราวเก็บจำนวน และอีกตัว temp เริ่มต้นที่ 2
- ตั้งค่า num เป็น temp = temp % mod
- เริ่มลูป while num > 0
- ตรวจสอบ IF 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)
// ฟังก์ชันวนซ้ำหา (x^y)%p ใน O(log y)
ll power(ll x, ll y, ll p){
ll result = 1;
x = x % p;
while (y > 0){
if (y & 1){
result = (result * x) % p;
}
y = y >> 1;
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;
}เอาต์พุต
count is: 8
