Solutions of Fences painting

Select solution language

KevinLe0801 Created at 6 likes

Gọi $f[i]$ là số cách sơn rào màu cam từ vị trí $1$ đến vị trí $i$ **Trường hợp cơ sở**: Dễ dàng nhận thấy chỉ có duy nhất 1 cách sơn màu cam cho các vị trí từ $1$ đến $k$ Với $i > k$, ta tính $f[i]$ bằng tổng các giá trị $f[j]$ với $j \in [1;i-k]$ rồi cộng thêm $1$, hay như có công thức sau: $\sum_{j=1}^{i-k} f[j]$ $+ 1$ (Quy tắc cộng), có thể tính được bằng cách sử dụng mảng tiền tố Cuối cùng, ta có đáp án là $f[n] + 1$ (tính thêm trường hợp không sơn rào cam) **Code solution** ```cpp= #include <bits/stdc++.h> #define ll long long using namespace std; const int MAXN = 2 * 1e5 + 7; const int MOD = 1e9 + 7; int f[MAXN]; int pf[MAXN]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; for (int i = 1; i <= k; i++){ pf[i] = pf[i-1] + 1; f[i] = 1; } for (int i = k+1; i <= n; i++){ f[i]= (1 + pf[i - k] % MOD) % MOD; pf[i] = (pf[i-1] % MOD + f[i] % MOD) % MOD; } cout << pf[n] + 1; return 0; } ```