Hướng dẫn giải của Tế bào X
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ả:
Thuật toán
Trường hợp ~n \le 10^6~.
Nhận xét: sau ~i~ đơn vị thời gian, tế bào ~X~ sẽ tăng thêm ~2^i~ tế bào.
Bài toán đưa về: tính tổng của dãy số ~1+2^1+2^2+...+2^n~.
Gọi ~res~ là kết quả bài toán. Duyệt ~i~ từ ~1~ đến ~n+1~, với mỗi ~i~ ta thêm ~2^i~ vào ~res~.
ĐPT: ~O(n)~.
Code tham khảo
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
// if (fopen("nhap.inp", "r"))
// freopen("nhap.inp", "r", stdin);
int n;
cin >> n;
int res = 0, Pow2 = 1;
for(int i = 1; i <= n + 1; ++i) {
res = (res + Pow2)%MOD;
Pow2 = (Pow2 * 2)%MOD;
}
cout << res;
return 0;
}
Trường hợp ~n \le 10^{18}~.
Ta có: ~1+2^1+2^2+...+2^n=2^{n+1}-1~.
Chứng minh:
Đặt ~S~ = ~1+2^1+2^2+...+2^n~
~\Rightarrow~ ~2.S=2^1+2^2+...+2^n~
~\Rightarrow~ ~2.S-S=2^1+2^2+...+2^{n+1}-(1+2^1+2^2+...+2^n)~
~\Rightarrow~ ~S=2^{n+1}-1~
Vậy ~1+2^1+2^2+...+2^n=2^{n+1}-1~.
Ta sẽ tính ~2^{n+1}~ trong ~O(log_2n)~ bằng chia để trị. Tìm hiểu thêm tại: https://vnoi.info/wiki/translate/he/Number-Theory-3.md
ĐPT: ~O(log_2n)~
Code tham khảo
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int POW2(long long i) {
if (i == 1) return 2;
if (i == 0) return 1;
int tmp = POW2(i/2);
if (i%2) return 1ll * tmp * tmp * 2 %MOD;
else return 1ll * tmp * tmp %MOD;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
// if (fopen("nhap.inp", "r"))
// freopen("nhap.inp", "r", stdin);
long long n;
cin >> n;
cout << (POW2(n + 1) - 1 + MOD)%MOD;
return 0;
}
Bình luận