你加的时候没 mod 10,做减法只加一个 10 会出错
by liaiyang @ 2024-02-19 19:19:57
@[coder2009](/user/675208) 有没有一种可能需要在中间取模。
```cpp
// 题目: P4141 消失之物
// 链接: https://www.luogu.com.cn/problem/P4141
// 难度: 普及/提高−
// 题解: https://www.luogu.com.cn/problem/solution/P4141
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e3 + 5;
int dp[maxn], w[maxn];
void best_coder() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> w[i];
}
dp[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = m; j >= w[i]; --j) {
dp[j] = (dp[j] + dp[j - w[i]]) % 10;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j >= w[i]) {
dp[j] -= dp[j - w[i]];
dp[j] %= 10;
dp[j] += 10;
dp[j] %= 10;
}
cout << (dp[j] + 10) % 10;
}
for (int j = m; j >= w[i]; --j) {
dp[j] += dp[j - w[i]];
dp[j] %= 10;
}
cout << '\n';
}
}
void happy_coder() {
}
signed main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
```
by QWQ_123 @ 2024-02-19 19:20:40
@[QWQ_123](/user/740328) 因为数字太大 `#define int long long`,还是会出现负数
by QWQ_123 @ 2024-02-19 19:21:05
@[liaiyang](/user/783170)
谢大佬!改后AC了
```cpp
for (int i = 0; i < n; ++i) {
for (int j = m; j >= w[i]; --j) {
dp[j] += dp[j - w[i]];
dp[j] %= 10;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j >= w[i]) {
dp[j] -= dp[j - w[i]];
dp[j] %= 10;
}
cout << (dp[j] + 10) % 10;
}
for (int j = m; j >= w[i]; --j) {
dp[j] += dp[j - w[i]];
dp[j] %= 10;
}
cout << '\n';
}
```
by coder2009 @ 2024-02-19 20:56:03
@[QWQ_123](/user/740328) 中间需要取模!
by coder2009 @ 2024-02-19 20:58:32
@[coder2009](/user/675208) ?
by QWQ_123 @ 2024-02-19 20:59:05
那个代码AC了啊(
by QWQ_123 @ 2024-02-19 20:59:25
@[coder2009](/user/675208) 我想表达的意思是dp数组中间的值很大,longlong也存不下,所以中间必须取模,然后可以看到我改的您的代码了也加了取模(/kk
by QWQ_123 @ 2024-02-19 21:00:33
@[QWQ_123](/user/740328)
就是中间需要取模啊,该后的AC代码
```cpp
// 题目: P4141 消失之物
// 链接: https://www.luogu.com.cn/problem/P4141
// 难度: 普及/提高−
// 题解: https://www.luogu.com.cn/problem/solution/P4141
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
int dp[maxn], w[maxn];
void best_coder() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> w[i];
}
dp[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = m; j >= w[i]; --j) {
dp[j] += dp[j - w[i]];
dp[j] %= 10;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j >= w[i]) {
dp[j] -= dp[j - w[i]];
dp[j] %= 10;
}
cout << (dp[j] + 10) % 10;
}
for (int j = m; j >= w[i]; --j) {
dp[j] += dp[j - w[i]];
dp[j] %= 10;
}
cout << '\n';
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
```
by coder2009 @ 2024-02-19 21:00:41
@[QWQ_123](/user/740328)
嗯,明白了
by coder2009 @ 2024-02-19 21:01:52