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; }
