−目次

AtCoder Beginner Contest 336 F,G問題メモ
- F - Rotation Puzzle
  - 問題
  - 解法
- G - 16 Integers
  - 問題
  - 解法

AtCoder Beginner Contest 336 F,G問題メモ

AtCoder Beginner Contest 336

今や、Eくらいの桁DPだと水Diffなんですねえ。しっかり青ありそうと感じていたが。

F - Rotation Puzzle

問題

$H \times W$ の盤面に、 $1～HW$ の数字が1つずつ書かれている
以下の操作を20回まで行える
- 盤面より縦横1つ小さい $(H-1) \times (W-1)$ の長方形を選び、それを180度回転する
盤面を整列する（Row Major Order に $1,2,...,HW$ が書かれた状態にする）までの最小手数を求めよ
- ただし、20回で不可能なら-1
$3 \le H,W \le 8$

解法

1回の操作でとりうる選択肢は、4通りしかない。

まず、「たとえば ↖左上、↗右上の順に操作するとシンプルな1つの操作と見なせる」みたいな、一見、複雑な操作でも2個まとめることでわかりやすくならないかな？と考えたが、実際にやってみても今ひとつシンプルにならない。

じゃあ、制約が小さいので、盤面まるごと状態に持ったBFSはどうか、というと、こちらは 20回で見つからなければ打ち切っていいという設定もあり、いけそう。

だが、状態数を見積もると、直前に行った操作を繰り返すのは無駄なので2手目以降は選択肢が3つに減るとしても、 20手までの全状態は $\displaystyle \sum_{i=0}^{19} 4 \times 3^i \simeq 7 \times 10^9$ となり、さすがに制限時間が厳しい。

しかし、10手くらいなら $\displaystyle \sum_{i=0}^{9} 4 \times 3^i \simeq 1.2 \times 10^5$ 程度なので、実際に盤面を反転させる操作に $HW$ かかるとしても、十分に全探索できる。

初期盤面と目標盤面のそれぞれから上限10手分だけ探索を進めると、両方から同じ盤面に到達できる中で、合計最短手数の少ないものが答えとなる。

双方向探索

多分、問題が最初からグラフの形だったら「双方向探索しなさい」という意図が分かりやすくなってもう少し簡単になってそう。
盤面を回転させる、盤面ごと状態に持つ、という重実装系の要素が目眩ましとなっていた感がある。

実装

Numpyを使うと、2次元配列の反転は a[::-1, ::-1] と書けるので、幾分か実装が楽。

だが、BFSで距離などを記録する際、盤面のnumpy.arrayをそのまま辞書型のキーにすることはできない。（Hashableでないので）

a.data.tobytes() とすると、盤面aの状態を一意に表すHashableな値に、そこそこ高速に変換できる。

Python3

G - 16 Integers

問題

$X_{0,0,0,0}～X_{1,1,1,1}$ の、4つの $\{0,1\}$ を添字に持つ16個の整数が与えられる
その合計値を $N$ とする
以下の条件を満たす長さ $N+3$ の数列 $A=(A_1,...,A_{N+3})$ としてあり得るものの個数を、 $\mod{998244353}$ で求めよ
- $A$ の要素は全て $\{0,1\}$
- 全ての $(i,j,k,l)$ に対して、 $A$ 中で $(i,j,k,l)$ の並びはちょうど $X_{i,j,k,l}$ 個ある
  - 例えば、 $A$ 中で $...,0,1,0,1,...$ という並びが出現する箇所は $X_{0,1,0,1}$ 個ある
$1 \le N \le 10^6$

解法

公式Editorialを参考にしての自分なりのメモ。

テクニック（公式）を知っていないとわりとどうにもならない（本番中に自力で導出・証明するのは現実的で無さそう）。
また、問題をそのテクニックに適用するにも考察が必要。

ただ、テクニックへの当てはめ方さえ分かれば、アドホックに実装する部分は少なめかな。

グラフの問題に変換

3つの並び $(0,0,0)～(1,1,1)$ を表す8頂点を用意し、例えば $(0,1,0,1)$ は $(0,1,0)→(1,0,1)$ の移動として捉える。

すると、「グラフ上のどこか適当な頂点から開始し、 $(i,j,k)→(j,k,l)$ への移動を合計 $X_{i,j,k,l}$ 回、全ての $(i,j,k,l)$ に対しておこない、適当な頂点で終了する」ような動きを、何通り作れますか、という問題になる。

さらに移動回数分だけ多重辺として複製してやると、「全ての道を1回ずつ通る経路（オイラー路）が何通りありますか」という問題になる。

有向グラフがオイラー路を持つ必要十分条件は、以下となる。

（次数が0でない）全ての頂点が連結
各頂点の入次数と出次数について、以下のいずれか
- 全ての頂点について、入次数と出次数が等しい
- 入次数が出次数より1だけ小さい頂点が1つ、1だけ大きい頂点が1つあり、他は全て等しい

これに該当しない入力は“0”と出力して終了。
以下、この条件は満たすとする。

BEST Theorem

有向オイラーグラフに対して、そのオイラー閉路を数え上げる公式。

BEST_theorem
- “BEST” は、提案した4名の名前のイニシャルから取られているらしい
適用条件
- 自己ループや多重辺を含んでいてもよい
- 頂点と辺は全て区別する（多重辺であっても）

ここで、似た言葉が出てくるので確認しておくと、有向グラフにおいて、

オイラー路
- 全ての道を1回ずつ通る経路。始点と終点が別でもいい
オイラー閉路（オイラー回路）
- 全ての道を1回ずつ通り、始点に戻ってくる経路
オイラーグラフ
- オイラー閉路を持つようなグラフ
- ＝全ての頂点で、入次数＝出次数となっているグラフ

今回求めたいのは“オイラー路”の数だが、BEST Theorem が求めるのは“オイラー閉路”の数。
さて、どうするか。

オイラー路の始点と終点を固定すると、終点→始点に辺を1本追加した経路はオイラー閉路となる。
辺は全て区別されるので、「辺を追加したグラフでオイラー閉路を1つ見つけ、追加辺で切り開く」とオイラー路と1対1対応する。
これで、BEST Theorem からオイラー路を数えられる。

始点・終点の決め方のパターンとしては、

グラフに入次数が出次数より1小さい/大きい頂点が1つずつある場合、そこが始点/終点で確定する
全ての入次数と出次数が等しい場合、そこから作られるオイラー路は既にオイラー閉路であり、どの頂点でも始点・終点と見なせる。
- 始点かつ終点とする頂点（最大8通り）を全て試し、結果を合計すればよい

BEST Theorem では、オイラー閉路の数は以下の式で与えられる。

$\displaystyle ec(G)=t_{w}(G) \prod_{v \in V}(deg(v)-1)!$

$t_{w}(G)$ は、頂点 $w$ を根とする有向全域木の個数
- 行列木定理（有向グラフバージョン）によって求められる
- Kirchhoff's theorem - Wikipedia
  - 以下の正方行列を作成する
    - $q_{i,j}$ には $i→j$ への辺の数の-1倍
    - $q_{i,i}$ には $i$ の自己ループを除いた入次数
  - $i$ 番目の行と列を除いた行列の行列式が、 $t_{i}(G)$
- オイラーグラフの場合、 $w$ に依らず全頂点で同じ値になる
$deg(v)$ は $v$ からの出次数

無向グラフの行列木定理ではラプラシアン行列の余因子を求めるが、やることはよく似ている。
有向グラフの場合、行列の作り方、削除する行と列は $i=j$ でないとダメな点、（オイラーグラフでない一般の場合） $i$ によって結果が変わる点、などが無向グラフとは異なるが、ある程度は有向グラフでも無向版のライブラリを流用できる。

行列木定理ではループは考慮されないので、ループだけしか含まれない入力（ $X_{0,0,0,0}$ のみ正で、他は0など）では、行列式を計算すべき行列が空になり、実装によっては変になりうる。
コーナーケースとして別途処理するのが安心かも。

Python3

細かいことだけど、Numpyのboolean-indexで ATrue, False, True としたら $A$ の $0,2$ 行目が抽出された新たな配列ができるけど、これを2次元にした場合 ATrue, False, True], [False, True, True は $[A[0,1], A[2,2]]$ という「対角成分の1次元配列」になって（Trueの数が合わないとそもそもエラー）、それぞれがTrueの行・列を抜き出した2次元配列にはなってくれないんだね。

        
          
          
              
              import numpy as np
from numba import njit
 
 
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x
 
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True
 
    def get_size(self, x):
        return -self.table[self.root(x)]
 
 
def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs
 
 
@njit('(i8[:,:],i8)', cache=True)
def determinant(matrix, MOD):
    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a > 0:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret
 
    n, m = matrix.shape
    assert n == m
 
    det = 1
    for i in range(n - 1):
        if matrix[i, i] == 0:
            for k in range(i + 1, n):
                if matrix[k, i] != 0:
                    matrix[i], matrix[k] = matrix[k], matrix[i]
                    det *= -1
                    det %= MOD
                    break
            else:
                return 0
        inv = mod_pow(matrix[i][i], MOD - 2, MOD)
        for k in range(i + 1, n):
            if matrix[k, i] != 0:
                r = matrix[k, i] * inv % MOD
                for j in range(i, n):
                    matrix[k, j] -= r * matrix[i, j]
                    matrix[k, j] %= MOD
        det *= matrix[i, i]
        det %= MOD
    return det
 
 
def solve(xxx):
    in__deg = [0] * 8
    out_deg = [0] * 8
    matrix = np.zeros((8, 8), np.int64)
    MOD = 998244353
 
    # コーナー処理
    if sum(xxx[1:]) == 0:  # X0000 のみ
        return 1
    if sum(xxx[:-1]) == 0:  # X1111 のみ
        return 1
    if sum(xxx[1:-1]) == 0:  # X0000 と X1111 が両方あり、他が無い
        return 0
 
    uft = UnionFind(8)
    use_vertices = set()
 
    for i in range(16):
        x = xxx[i]
        if x == 0:
            continue
        u = i >> 1
        v = i & 0b111
        out_deg[u] += x
        in__deg[v] += x
        matrix[u, v] -= x
        uft.unite(u, v)
        use_vertices.add(u)
        use_vertices.add(v)
 
    # 連結性チェック
    leaders = {uft.root(i) for i in use_vertices}
    if len(leaders) != 1:
        return 0
 
    # 自明な始点と終点があるか調べる
    s = -1
    g = -1
    for i in range(8):
        if in__deg[i] == out_deg[i]:
            continue
        if in__deg[i] + 1 == out_deg[i]:
            if s != -1:
                return 0
            s = i
        elif in__deg[i] == out_deg[i] + 1:
            if g != -1:
                return 0
            g = i
        else:
            return 0
 
    for i in range(8):
        matrix[i, i] += out_deg[i]
 
    facts, finvs = precompute_factorials(1_000_000, MOD)
 
    if s == g == -1:
        # 全ての入次数＝出次数 なので、最初と最後が同じ並びのものを全探索
        # matrix に関しては、どの頂点を始点・終点と仮定しても自己ループ辺が追加されるだけなので変化が無い＝1回だけ計算して値を使い回せる
        is_zero_row = np.all(matrix == 0, axis=1)
        is_zero_col = np.all(matrix == 0, axis=0)
        assert (is_zero_row == is_zero_col).all()
        matrix = matrix[~is_zero_row][:, ~is_zero_col]
        det = int(determinant(matrix, MOD))
 
        ans = 0
        for g in use_vertices:
            tmp = 1
            for j in use_vertices:
                od = out_deg[j] + 1 if j == g else out_deg[j]
                tmp *= facts[max(1, od - 1)]
                tmp %= MOD
            ans += det * tmp % MOD
        ans %= MOD
    else:
        # 始点と終点は決まっている
        matrix[g, s] -= 1
        matrix[g, g] += 1
 
        is_zero_row = np.all(matrix == 0, axis=1)
        is_zero_col = np.all(matrix == 0, axis=0)
        assert (is_zero_row == is_zero_col).all()
        matrix = matrix[~is_zero_row][:, ~is_zero_col]
        det = int(determinant(matrix, MOD))
        tmp = 1
        for j in use_vertices:
            od = out_deg[j] + 1 if j == g else out_deg[j]
            tmp *= facts[max(0, od - 1)]
            tmp %= MOD
        ans = det * tmp % MOD
 
    # 辺は区別しないので並び方の分を減らす
    for x in xxx:
        ans *= finvs[x]
        ans %= MOD
 
    return ans
 
 
xxx = list(map(int, input().split()))
ans = solve(xxx)
print(ans)

            

        
      