Solutions of Fences painting

Select solution language

KevinLe0801 Created at 16 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; } ```

Long4200 Created at 0 likes

## Ý tưởng rất đơn giản như sau: ### Xét từng tấm gỗ từ 1 -> n. ### tấm thứ i, có hai cách: - Sơn vàng: số cách ở tấm i sẽ bằng i − 1 tấm đằng trước (chỉ thêm một tấm vàng, không ảnh hưởng k/c cam). - Sơn cam: Để tấm i là cam, mọi tấm cam trước đó phải cách ít nhất k vị trí. Nghĩa là, nếu i < k, thì phía trước chưa thể có cam nào vi phạm, nên có đúng 1 cách cho việc này (toàn bộ tấm 1…i−1 là vàng, rồi tới i mới cam). Còn nếu i ≥ k, thì các vị trí từ i−k+1 đến i−1 buộc phải sơn vàng, và phần còn lại (1…i−k) là các cách thỏa mãn từ trước. ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; const ll MOD = 1e9 + 7; const ll maxN = 1e6 + 5; ll n, k, dp[maxN]; int main() { cin >> n >> k; dp[0] = 1; // luôn có cách cho không sơn tấm cam for(int i = 1; i <= n; i++) { if(i <= k) dp[i] = dp[i - 1] + 1; else dp[i] = (dp[i - 1] % MOD + dp[i - k] % MOD) % MOD; } cout << dp[n]; } ```