arc115

NISHIO Hirokazu [Translate]
ARC115

A - Two Choices
SiとSjの回答が食い違っている箇所はS_i \oplus S_j
食い違ってる箇所が偶数なら正解数が一致する可能性があり、奇数なら可能性がない
というわけで各桁についてxorを取って1かどうかを見れば良い: \bigoplus (S_i \oplus S_j)
ここで、xorは結合法則を満たす演算だから順番を変えてもよい: \bigoplus (S_i) \oplus \bigoplus (S_j)
これではまだiとjについてループするので10^10回の計算が必要になってしまう
これをどうするか？
→典型的アプローチ頻度表
値の種類KがNよりだいぶ少ないときに使えるテクニック
O(N)払って種類ごとの個数を先に求める
そうすると同じ値の組み合わせの計算はまとめて実行可能になるので、O(N^2) \to O(K^2)となる
今回はK=2
O(N)払って\bigoplus (S_i)が1であるものの個数xを先に求める
\sum_{ij} \left(\bigoplus S_i\oplus \bigoplus S_j\right) = x^2(1 \oplus 1) + x(N-x)(1 \oplus 0) + (N-x)x(0 \oplus 1) + (N-x)^2(0 \oplus 0) = 2x(N-x)
これはi, jの大小を区別してないので行列の半分にして答えが求まる
pythondef main():
    N, M = map(int, input().split())
    s1 = 0
    for i in range(N):
        S = input().strip()
        s = S.count(b"1")
        if s % 2:
            s1 += 1
    print(s1 * (N - s1))

B - Plus Matrix
条件を満たすA, Bが存在するなら R_j = \sum_i C_{ij} = \sum_i A_i + NB_j
\min(R_j) = \sum_i A_i + N\min(B_j)だが、\min(B_j) = 0として構わない
\min(B_j) = m > 0の時、すべてのBからmを引いて、すべてのAにmを足しても結果が変わらないから
というわけで \min(R_j) = \sum_i A_iだから、 B_j = (R_j - \min(R_j)) / N、A_i = C_{i1} - B_1
求めたA, Bで再度Cを求めて、正しく構築できてるか確認する
pythondef solve(N, CS):
    sums = [sum(row) for row in CS]
    m = min(sums)
    if any((x - m) % N for x in sums):
        return ()

    AS = [(x - m) // N for x in sums]
    BS = [x - AS[0] for x in CS[0]]
    if any(x < 0 for x in BS):
        return ()
    NCS = [tuple(AS[i] + BS[j] for j in range(N)) for i in range(N)]
    if NCS != CS:
        return ()
    return (AS, BS)

C - ℕ Coloring
まず小さい方から考える
ここまで描いた時点で「ああ、素因数の個数ね」と気づく
証明
素因数の個数がK個であるもの同士は互いに約数になることはない
だから同じ色で塗って良い
素因数の個数がK個であるものは素因数の個数がK未満の約数を必ず1つ以上持つ
だからそれらと異なる色でなければならない
pythondef main():
    N = int(input())
    ret = []
    for i in range(1, N + 1):
        f = get_factors(i)
        x = sum(f.values()) + 1
        ret.append(x)
    print(*ret)

D - Odd Degree
しばらく眺めて「連結成分を求める必要がありそうだな」とは思ったがそこから先がわからないのでまず全探索で解くコードをつくった
pythondef blute(N,M,edges,edgelist):
    ret = [0] * (N + 1)
    for i in range(2 ** M):
        deg = [0] * N
        for j in range(M):
            if i & (1 << j):
                a, b = edgelist[j]
                deg[a] += 1
                deg[b] += 1
        r = sum(x % 2 for x in deg)
        ret[r] += 1
    return ret
観察してわかったこと
連結でない場合はそれぞれを求めて畳み込み
実装
UnionFindで連結成分の頂点と辺の数を数える
逆数・階乗テーブルを作って置いて連結成分ごとに計算
それぞれを畳み込み
結果TLE
コンテスト後AC
TLEの原因: 畳み込みの計算にFFTライブラリを使ったこと
素朴なループで畳み込めばACだった
pydef solve(N,M,edges,edgelist):
    init_unionfind(N)
    for x, y in edgelist:
        unite(x, y)
    comps = []
    for x in range(N):
        if find_root(x) == x:
            comps.append((num_edges[x], num_vertex[x]))

    MOD = 998_244_353
    comb = CombinationTable(N + 10, MOD).comb

    ret = None
    for e, v in comps:
        xs = [0] * (v + 1)
        xs[0] = 1
        for i in range(1, (v // 2) + 1):
            xs[i * 2] = comb(v, 2 * i)
        if e > v - 1:
            m = pow(2, e - (v - 1), MOD)
            xs = [x * m % MOD for x in xs]
        if ret is None:
            ret = xs
        else:
            ys = ret
            ret = [0] * (len(xs) + len(ys) - 1)
            for i in range(len(xs)):
                for j in range(len(ys)):
                    ret[i + j] += xs[i] * ys[j]
                    ret[i + j] %= MOD
    return ret            