giải bằng c++ và phương pháp quy hoạch động Chia kẹo CHIAKEO,Tí có n túi kẹo. Túi thứ i có i cái kẹo. Tí định chia cho Tèo một nửa số kẹo,mình đang có và đương nhiên sẽ không phải bóc kẹo trong túi ra chia. Tí băn,khoan là có bao nhiêu cách để chia đều số kẹo của mình cho Tèo.,Yêu cầu: Tính số cách mà Tí có thể chia đều số kẹo của mình thành hai,phần bằng nhau.,Ví dụ: nếu $n=7,$ có 4 cách như sau:,{1,3,4,6} và {2,5,7},{1,2,5,6} và {3,4,7},{1,2,4,7} và {3,5,6},{1,6,7} và {2,3,4,5},Đầu vào,+ Dòng đầu tiên và duy nhất chứa số nguyên $N(1\leq N\leq500).$,Đầu ra,+ In câu trả lời theo modulo $10^9+7.$,

,output
7,4

Question

giải bằng c++ và phương pháp quy hoạch động Chia kẹo CHIAKEO,Tí có n túi kẹo. Túi thứ i có i cái kẹo. Tí định chia cho Tèo một nửa số kẹo,mình đang có và đương nhiên sẽ không phải bóc kẹo trong túi ra chia. Tí băn,khoan là có bao nhiêu cách để chia đều số kẹo của mình cho Tèo.,Yêu cầu: Tính số cách mà Tí có thể chia đều số kẹo của mình thành hai,phần bằng nhau.,Ví dụ: nếu $n=7,$ có 4 cách như sau:,{1,3,4,6} và {2,5,7},{1,2,5,6} và {3,4,7},{1,2,4,7} và {3,5,6},{1,6,7} và {2,3,4,5},Đầu vào,+ Dòng đầu tiên và duy nhất chứa số nguyên $N(1\leq N\leq500).$,Đầu ra,+ In câu trả lời theo modulo $10^9+7.$,

,output
7,4

promiseladyy · Accepted Answer

```cpp
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
int n;
cin >> n;

vector<int> dp(n * (n + 1) / 2 + 1, 0);
dp[0] = 1;

if ((n * (n + 1) / 2) % 2 != 0) {
cout << "0" << endl; // Nếu tổng số kẹo không chia hết cho 2, không có cách chia đều
return 0;
}

int target = n * (n + 1) / 4;

for (int i = 1; i <= n; i++) {
for (int j = target; j >= i; j--) {
dp[j] = (dp[j] + dp[j - i]) % MOD;
}
}

cout << dp[target] << endl;

return 0;
}
```

Timi · Answer

Để giải bài toán chia kẹo bằng C++ và phương pháp quy hoạch động, bạn có thể sử dụng thuật toán sau: ```cpp #include using namespace std; const int MOD = 1e9 + 7; int main() { int n; cin >> n; vector dp(n * (n + 1) / 2 + 1, 0); dp[0] = 1; if ((n * (n + 1) / 2) % 2 != 0) { cout << "0" << endl; // Nếu tổng số kẹo không chia hết cho 2, không có cách chia đều return 0; } int target = n * (n + 1) / 4; for (int i = 1; i <= n; i++) { for (int j = target; j >= i; j--) { dp[j] = (dp[j] + dp[j - i]) % MOD; } } cout << dp[target] << endl; return 0; } ``` Trong đó, ta sử dụng mảng `dp` để lưu trữ số cách chia kẹo sao cho tổng số kẹo của mỗi phần bằng nhau. Sau đó, sử dụng vòng lặp để tính toán các trường hợp có thể xảy ra và in ra kết quả theo modulo $10^9+7$. Với input là `7`, output sẽ là `4` theo modulo $10^9+7$.