

Link bài:
Thuật toán:
Code:
Thuật toán:
- Nhận xét: Ở trường hợp n = 0, ta chỉ có 1 cách xếp các ô gạch.
- Trường hợp n = 1, ta có 3 cách xếp các ô gạch trên.
- Gọi số cách điểm xuyết của i ô gạch là ai: Với tường hợp thứ i (i > 1) ta có nhận xét sau:
- Nếu ô gạch thứ i-1 có điểm xuyết là 1 0 thì ở ô thứ i, điểm xuyết là 0 0 hoặc 0 1.
⇒ Với số cách điểm xuyết e sao cho ô i-1 có điểm xuyết 1 0, ta có 2*e cách điểm xuyết ô thứ i.
- Tương tự ô gạch i-1 có điểm xuyết 0 1 thì ô thứ i, điểm xuyết là 0 0 hoặc 1 0.
⇒ Với số cách điểm xuyết e2 sao cho ô i-1 có điểm xuyết 0 1, ta có 2*e2 cách điểm xuyết ô thứ i.
- Nếu ô gạch thứ i-1 có điểm xuyết là 0 0 thì ô thứ i, điểm xuyết là 0 1, 1 0 hoặc 0 0.
⇒ Với số cách điểm xuyết e3 sao cho ô i-1 có điểm xuyết 0 0, ta có 3*e3 cách điểm xuyết ô thứ i.
Ở điểm xuyết ô i-1 là 0 0, có thể chia thành trường hợp sau:
- Trường hợp ô i điểm xuyết 0 1 và 1 0. Có 2*e3 trường hợp
- Trường hợp ô i điểm xuyết 0 0 (tức sẽ bằng toàn bộ số cách điểm xuyết của ô i-2) (Ô i-1 và ô i đều có điểm xuyết 0 0).
Tức công thức của ta là: Ai = a (i-1) *2+a (i-2)
Code:
Mã:
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1007];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("laga.inp", "r", stdin);
//freopen("laga.out", "w", stdout);
cin >> n;
a[0] = 1; a[1] = 3;
if (n <= 1) cout << a[n]; else{
for (int i = 2; i <= n; i++) a[i] = (a[i-1]*2 + a[i-2])%100000000;
cout << a[n];
}
return 0;
}