Xor Array [Kyoto University Programming Contest 2020 Spring D]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/D

前提知識

• 累積和による動的計画法高速化

前提知識

DPの作り方で運命が変わる。 dp[i][xo][lst] := 数列のi個目まで確定していて、総XORがxoで、最後の要素がlstであるときの組み合わせ これで先頭から埋めていくように更新していくのは更新の高速化が見込めない。 これで、次の要素を追加するときにlst以上の数を指定するので、全体でO(N⁴)であるが、 次の追加要素が決まるたびにxorが変わり（代入先に規則性がない）、まとめて高速化もしずらい。

dp[lst][xo][cnt] := 数列で数lst以前まで使用していて、総XORがxoで、先頭のcnt個数が確定しているときの組み合わせ 順番を変えただけっぽいが、このようにすると、次に使用する数が固定され、xor計算を単純化できる。 具体的にはソースコードに埋め込みで、改善過程を書いておいた。 よくある「配るDP→貰うDP→累積和で高速化」の流れである。

int N, X;
mint dp[2][512][512];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;

    dp[0][0][0] = 1;
    rep(lst, 0, X + 1) {
        int cu = lst % 2;
        int ne = 1 - cu;

        rep(xo, 0, 512) rep(cnt, 0, N + 1) dp[ne][xo][cnt] = 0;

        // 1. 配るDP
        /*rep(xo, 0, 512) rep(cnt, 0, N + 1) {
            rep(d, 0, N + 1) {
                int xo2 = xo;
                if (d % 2 == 1) xo2 ^= lst;
                dp[ne][xo2][cnt + d] += dp[cu][xo][cnt];
            }
        }*/

        // 2. 貰うDP
        /*rep(xo, 0, 512) rep(cnt, 0, N + 1) {
            rep(d, 0, cnt + 1) {
                int xo2 = xo;
                if (d % 2 == 1) xo2 ^= lst;
                dp[ne][xo][cnt] += dp[cu][xo2][cnt - d];
            }
        }
        */

        // 3. 偶奇で分けて高速化
        rep(xo, 0, 512) {
            mint odd = 0, even = 0;
            mint odd_xor = 0, even_xor = 0;
            rep(cnt, 0, N + 1) {
                if (cnt % 2 == 0) {
                    even += dp[cu][xo][cnt];
                    even_xor += dp[cu][xo ^ lst][cnt];
                }
                else {
                    odd += dp[cu][xo][cnt];
                    odd_xor += dp[cu][xo ^ lst][cnt];
                }

                if (cnt % 2 == 0) dp[ne][xo][cnt] = odd_xor + even;
                else dp[ne][xo][cnt] = odd + even_xor;
            }
        }
    }

    cout << dp[(X+1) % 2][X][N] << endl;
}