Cuối cùng cũng xong cách O(log^2 n)
https://leetcode.com/submissions/detail/806772612/
https://leetcode.com/submissions/detail/806772612/
Ngoài việc chia các đoạn với các bit nhỏ. Thì trong trường hợp n không phải dạng 2^k-1 cần phải chia tiếp như sau.
Giả sử n = 1001'0011. Tính từ bit 1 thứ 2 từ phải sang:
Tẩ cả các đoạn trên đều có độ dài dạng 2^k và có thể áp dụng thuật toán O(k) để tính tổng.
Giả sử n = 1001'0011. Tính từ bit 1 thứ 2 từ phải sang:
- 1001'0011: [1000'0000 -> 1000'1111]
- 1001'0011: [1001'0000 -> 1001'0001]
- 1001'0011: [1001'0010 -> 1001'0011]
Tẩ cả các đoạn trên đều có độ dài dạng 2^k và có thể áp dụng thuật toán O(k) để tính tổng.
C++:
#define M 1'000'000'007
// return 2^x % M
uint64_t powM(uint64_t p, uint64_t x) {
uint64_t base = p, res = 1;
while (x) {
if (x & 1) res = (res * base) % M;
base = (base * base) % M;
x >>= 1;
}
return res;
}
uint64_t prod(uint64_t x, uint64_t y) {
return (x * y) % M;
}
uint64_t sum(uint64_t x, uint64_t y) {
x += y;
return x - (M & -(x >= M));
}
uint64_t diff(uint64_t x, uint64_t y) {
int d = (int) x - (int) y;
return d + (M & -(d < 0));
}
class Solution {
// k: number bit
// g: gap
// pk: 4^(k*(2^(k-2))) - 1
// p2gk: 2^(gk)
// -> sum from [end - l + 1 .. end]
uint64_t helper(uint64_t k, uint64_t pk, uint64_t p2gk, uint64_t l, uint64_t end, uint64_t g = 1)
{
if (g == l) return end;
auto p4gk = prod(p2gk, p2gk); // 4^(gk)
auto s1 = helper(k, pk, p4gk, l, end, g << 1);
// s0 = 2^(gk) { s1 - g * [4^(k*2^k) - 1] / [4^(gk) - 1] }
auto s0 = prod(
p2gk, // 2^(gk)
diff (
s1,
prod(
g,
prod(
pk,
powM(diff(p4gk, 1), M-2) // invmod of 4^(gk) -1 = (4^(gk) - 1) ^ (M - 2)
)
)
)
);
return sum(s0, s1);
}
public:
int concatenatedBinary(int n) {
if (n == 1) return 1;
uint64_t p2k = 4, // 2^k
p42k2 = 4, // 4^(2^(k-2)) = 2^(2^(k-1))
res = 1,
k = 2;
// sum from [1 .. 2^k)
for (; p2k <= n + 1;
p2k = sum(p2k, p2k), p42k2 = prod(p42k2, p42k2), ++k)
{
auto pk = powM(p42k2, k); // 4^(k*2^(k-2))
// p2gk = 2^(gk) = 2^k = p2k
// calculate sum from [ 2^(k-1) .. 2^k )
auto h = helper(k, diff(pk, 1), p2k, 1 << (k - 1), (1 << k) - 1, 1);
// res = h + res * 2^(k * 2^(k-1)) = res + h * pk
res = sum(prod(res, pk), h);
}
// return if n = 2^k-1
if (!(n & (n + 1))) return res;
// sum from [2^k .. n)
// check every 1-bit of n
for (int kk = k - 2; kk >= 1; --kk) {
if (n & (1 << kk)) {
auto l = 1 << kk;
auto pk = powM(p2k, l);
auto h = helper(k, diff(pk, 1), p2k, l, (n ^ l) | (l - 1), 1);
res = sum(prod(res, pk), h);
}
}
// last bit
if (n & 1) res = sum(prod(res, p2k), n^1);
res = sum(prod(res, p2k), n);
return res;
}
};
