Hướng dẫn giải của Cặp số OR
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Do ~A \vee B = 2^n-1~ có dạng ~11111 \dots 1111~ ở biểu diễn nhị phân, ta xét từng cặp chữ số của ~A, B~. Để chữ số thứ ~i~ của ~A \vee B~ bằng ~1~ thì chữ số thứ ~i~ của ~A~ và ~B~ phải là một trong các cặp ~(0, 1); (1, 0); (1, 1)~. Như vậy số các cặp ~A, B~ thỏa mãn sẽ là ~\frac{3^n+1}{2}~ do ~A, B~ có ~n~ chữ số và ~A \leq B~.
Do modulo đề cho là ~10^9+7~, để tính biểu thức này, ta cần áp dụng định lí Fermat nhỏ và thuật toán nhân Ấn Độ.
Như vậy, biểu thức cần tính sẽ là (power(3, n)+1)%MOD * power(2, MOD-2) % MOD.
Độ phức tạp: ~\mathcal{O}(\log n)~.
Bình luận