Bin_string
Cho một xâu nhị phân S, ban đầu S = "1"
Ta định nghĩa mộ phép biến đổi xâu nhị phân S như sau:
S = S + β(S) với β(α) là hàm đảo ngược xâu nhị phân α (1 thành 0 và 0 thành 1)
Như vậy:
- Sau 1 phép biến đổi,
S = "10" - Sau 2 phép biến đổi,
S = "1001" - Sau 3 phép biến đổi,
S = "10010110" - Sau 4 phép biến đổi,
S = "1001011001101001" - …
Cho một số n, hãy tính giá trị của số có biểu diễn nhị phân là xâu S sau khi thực hiện n biến đổi.
Vì đáp số có thể rất lớn nên hãy in ra số dư đáp án khi chia cho m
Ví dụ:
- Với
n = 3vàm = 4thìCalculatorString(n, m) = 2
Vì sau n = 3 phép biến đổi, S = “10010110”, S lúc này mang giá trị 150 chia m = 4 dư 2 nên đáp án là 2
Đầu vào/ Đầu ra:
- [Giới hạn thời gian chạy] 0.5s với C++, 3s với C# và Java, 4s với Python, Go và Js
- [Đầu vào] Integer n, m
1 ≤ n ≤ 107
2 ≤ m ≤ 109 + 7
- [Đầu ra] Integer
Giá trị của số có biểu diễn nhị phân là xâu S sau khi thực hiện n biến đổi và chia dư cho m
Post Comment