086 - Snuke's Favorite Arrays（★5）

[hxrxchang]

https://atcoder.jp/contests/typical90/tasks/typical90_ch

問題概要

x, y, z, w 形式のクエリがQ個与えられる。

• A[x] OR A[w] OR A[z] = w
• 各要素の値が 0 <= A[i] < 2 ** 60

以上の条件を満たす長さNの数列Aは何種類あるか求めよ。

解き方

全然分かっていない...

N = 3, Q = 1 のミニマムな入力を考えてみる

3 1
1 2 3 1

これの答えは 7 らしい。

数列A内の各要素は最大60bitだが、簡単のために4bitで考える。 3つの要素のAをbitにして表すと、

A: [xxxx, xxxx, xxxx]

で、それを縦に並べてみる

X: xxxx
Y: xxxx
Z: xxxx
-------
W: xxxx

X or Y or Z = 1 になるには、X, Y, Zのうち少なくとも1つが、1bit目が1になっていること。 そうすると、bit全探索の要領でパターンを列挙できる。 1bit目が経っているパターン (X), (X, Y), (X, Z), (X, Y, Z), (Y), (Y, Z), (Z) の7パターン。

なので、そのbitが立っているパターン数はbit全探索の計算量 (2 ** N = 2 ** 12 = 4096)かかる。 60bit全体だったら、4096 * 60 = 245760。 Q回行うから、245760 * 50 = 12288000 で間に合うということだろうか。

ここまでは理解できたが、それをコードに落とし込めていない。

写経したコード

https://github.com/E869120/kyopro_educational_90/blob/main/sol/086.cpp を写経。

var N, Q int
var x, y, z, w []int

func solve() {
    in := getInts()
    N, Q = in[0], in[1]
    X := make([]int, Q+1)
    Y := make([]int, Q+1)
    Z := make([]int, Q+1)
    W := make([]int, Q+1)
    for i := 1; i <= Q; i++ {
        in := getInts()
        X[i], Y[i], Z[i], W[i] = in[0], in[1], in[2], in[3]
    }

    x = make([]int, Q+1)
    y = make([]int, Q+1)
    z = make([]int, Q+1)
    w = make([]int, Q+1)
    ans := 1
    for i := 0; i < 60; i++ {
        for j := 1; j <= Q; j++ {
            x[j] = X[j]
            y[j] = Y[j]
            z[j] = Z[j]
            w[j] = (W[j] / (1 << i)) % 2
        }
        ret := bitZentansaku()
        ans *= ret
        ans %= MOD
    }
    fmt.Println(ans)
}

func bitZentansaku() int {
    ways := 0
    for i := 0; i < (1 << N); i++ {
        bit := make([]int, N+1)
        for j := 0; j < N; j++ {
            bit[j+1] = (i / (1 << j)) % 2
        }

        flag := true
        for j := 1; j <= Q; j++ {
            if ((bit[x[j]] | bit[y[j]]) | bit[z[j]]) != w[j] {
                flag = false
                break
            }
        }
        if flag {
            ways++
        }
    }
    return ways
}

https://atcoder.jp/contests/typical90/submissions/53987486