ハイパー部分和問題 [yukicoder 868]

https://yukicoder.me/problems/no/868

前提知識

• 戻すDP

解説

https://yukicoder.me/submissions/370474

戻すDPを知っている人は、適用するだけである。
まずは、普通にDPを作ろう。
dp[i][k] := 配列Aのi番目まで使って、総和がkである組み合わせ
戻すDPをするためにはtrue/falseでは行えないので、組み合わせにして解く。
漸化式を書くとdp[i+1][k] = dp[i][k] + dp[i][k-A[i]]である。
これで作るが、配列を後ろから埋めると節約できるタイプなので、
dp[k] := 総和がkである組み合わせ
を後ろから更新する。dp[k] += 前dp[k-A[i]]を後ろからすれば問題ない。

これをベースにしてDPを「戻す」
漸化式を変形すると、dp[i][k]=dp[i+1][k] - dp[i][k-A[i]]である。
これは先頭から更新していけば、dp[k]-=dp[k-A[i]]として戻すことができる。

戻したら、A[x]をvに更新して、遷移しなおす。
これでDPが再構築できるので、組み合わせ数が0より大きければ作成可能。
mod1つだと落ちる可能性があるので、modを複数個持つとHackには弱いが、フルフィードバックだと行けそう。
と思ったら、もうチャレンジケースが追加されてた。
こういう時は、素数を複数持って乱数で選択する。
計算量も若干余裕があったので、10種から2種選ぶようにした。
と思ったらTLEしたので、1種類でいった。
///////////////////////// writeup2 end *

int N, K, A[15101]; int Q;
const int MODS_COUNT = 1;
int dp[MODS_COUNT][50101];
const int MA = 15000;
int mods[10] = { 1000000007,1000000009,1000000021,1000000033,1000000087,1000000093,1000000097,1000000103,1000000123,1000000181 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    cin >> Q;

    rep(i, 0, 101) { int a = getrand(0, 9); int b = getrand(0, 9); swap(mods[a], mods[b]); }

    rep(mo, 0, MODS_COUNT) {
        dp[mo][0] = 1;
        rep(i, 0, N) if (0 < A[i]) rrep(k, MA * 2, 0) if (k + A[i] <= MA * 2) {
            dp[mo][k + A[i]] += dp[mo][k];
            dp[mo][k + A[i]] %= mods[mo];
        }
    }

    rep(q, 0, Q) {
        int x, v; cin >> x >> v;
        x--;

        // reverse
        if (0 < A[x]) {
            rep(mo, 0, MODS_COUNT) {
                rep(k, 0, MA * 2 + 1) if (0 <= k - A[x]) {
                    dp[mo][k] -= dp[mo][k - A[x]];
                    dp[mo][k] += mods[mo];
                    dp[mo][k] %= mods[mo];
                }
            }
        }

        // change
        A[x] = v;

        // remake
        rep(mo, 0, MODS_COUNT) {
            dp[mo][0] = 1;
            if (0 < A[x]) rrep(k, MA * 2, 0) if (k + A[x] <= MA * 2) {
                dp[mo][k + A[x]] += dp[mo][k];
                dp[mo][k + A[x]] %= mods[mo];
            }
        }

        // check
        bool ok = false;
        rep(mo, 0, MODS_COUNT) if (0 < dp[mo][K]) ok = true;
        if (ok) printf("1\n");
        else printf("0\n");
    }
}