XOR XorY [「みんなのプロコン 2018」 D]

https://beta.atcoder.jp/contests/yahoo-procon2018-qual/tasks/yahoo_procon2018_qual_d

解法

https://beta.atcoder.jp/contests/yahoo-procon2018-qual/submissions/2092050

考察がとても難しかった。
kmjpさんの解説と公式解説を丁寧に読み解くと理解できる。
考察過程を推測しながら、解説を書いていくことにする。
　
今回はルールが中々複雑なので、この複雑さをなんとか解消できないか考えてみよう。
KがO(10^3)なので、a[0]を全探索することで数え上げができそうである。
a[0]を固定して考えてみよう。
a[0]が固定されていると各a[i]は全て2択に絞られる
具体的には、a[i]は「A[0][i] ^ a[0] ^ X」か「A[0][i] ^ a[0] ^ Y」の二択。
もうちょっと書き換えてみると、a[i]は「α」か「α ^ X ^ Y」の二択になる。
この二択は、α≠βであれば「α」と「α^X^Y」と「β」と「β^X^Y」は全て別々になる。
つまり、二択の割り当ては「min(α,α^X^Y)」毎に独立に行えばいいということが分かる。
　
残っている問題としてA[0][?]についてはルールが守られているが、他のA[?][?]は正しくやれているかという問題がある。
ここからは大分推測なのだが、この問題まで考慮しだすと、複雑さがかなり増して800点では収まらない。
そのため、割り当てを1つ試してみて、ルールが全て満たされるなら、α^X^Yで変形しても大丈夫となるだろうという仮説を立てる。
実際をそれはあってそう（XかYのどちらかを任意に選べるため）。
　
後は、各グループ毎に割り当てを行っていくが、この時に以下の関数を使って組み合わせ数を計算する。
「f(n, a1, a2) := a1個のAとa2個のBからn個選んで並べる時の組合せ」
これはAを[0,a1]個選ぶ場合を全探索して、組合せ数を計算する。
各グループで関数fを呼び出すが、[0,a1]を全探索していくと、総和がNとなるので、ならしO(N^2)で出来る。

int N, K, X, Y;
int x[2050], A[1050][1050];
int cnt[5050], cnt2[5050];
int Z;
Comb<mint, 5050> com;
//---------------------------------------------------------------------------------------------------
map<int, mint> memo[1050][3030];
mint f(int n, int a1, int a2) {     // n枠にa1とa2を入れる組合せ
    if (a1 + a2 < n) return 0;
    if (n == 0 or a1 == 0 or a2 == 0) return 1;
    if (memo[n][a1].count(a2)) return memo[n][a1][a2];

    mint res = 0;
    rep(a, 0, a1 + 1) if (a <= n and n <= a + a2) res += com.aCb(n, a);
    return memo[n][a1][a2] = res;
}
//---------------------------------------------------------------------------------------------------
int solve() {
    rep(i, 0, N) cnt[x[i]]++;
    rep(y, 0, K) rep(x, 0, K) A[y][x] = min(A[y][x] ^ X, A[y][x] ^ Y);
    Z = X ^ Y;

    // 整合性チェック
    rep(y, 0, K) rep(x, 0, K) {
        if (y == x and A[y][x] != 0) return 0;
        if (y != x and A[y][x] != A[x][y]) return 0;
        if (y != x) {
            if ((A[0][x] ^ A[0][y]) == A[x][y]) continue;
            if ((A[0][x] ^ A[0][y] ^ Z) == A[x][y]) continue;
            return 0;
        }
    }

    mint ans = 0;
    rep(a0, 0, 2050) if (a0 < (a0 ^ Z)) {
        rep(i, 0, 2050) cnt2[i] = 0;
        cnt2[a0]++;
        rep(i, 1, K) cnt2[min(a0 ^ A[0][i], a0 ^ A[0][i] ^ Z)]++;
        mint d = 1;
        rep(i, 0, 2050) if (i < (i ^ Z)) d *= f(cnt2[i], cnt[i], cnt[i ^ Z]);
        ans += d;
    }
    return ans.get();
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> X >> Y;
    rep(i, 0, N) cin >> x[i];
    rep(y, 0, K) rep(x, 0, K) cin >> A[y][x];
    cout << solve() << endl;
}