P4141 消失之物(退背包模板)

P4141 消失之物

之前一直想学，然后咕咕咕了。（最后发现就是个容斥）

就是先考虑不退背包的情况，然后再容斥得出退背包的情况（就和硬币购物差不多）

采用滚动数组，注意枚举顺序（不退背包和退背包顺序是反的）。

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;
const ll MAXN = 1e6+10;

ll N, M, val[MAXN], f[MAXN][2];

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (ll i = 1; i <= N; i++) cin >> val[i];
    f[0][0] = f[0][1] = 1;
    for (ll i = 1; i <= N; i++) {
        for (ll j = M; j >= 1; j--) {
            if (j >= val[i]) f[j][0] += f[j - val[i]][0];
            f[j][0] %= 10;
        }
    }
    for (ll i = 1; i <= N; i++) {
        for (ll j = 1; j <= M; j++) {
            if (j >= val[i]) f[j][1] = (f[j][0] - f[j-val[i]][1] + 10) % 10;
            else f[j][1] = f[j][0] % 10;
            cout << f[j][1] % 10;
        }
        cout << endl;
    }
    return 0;
}