AtCoder Regular Contest++ 221 A,B,D問題メモ

AtCoder Regular Contest++ 221

Aがわからなすぎて滅。 構築のDのみを解いている人も一定数いたが、そっちに行くべきだったか？

A - Two Arithmetic Progressions

• 正整数 $N,A,B,C,D$ が与えられます．
• $\displaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D)$ を $998244353$ で割った余りを求めてください．ただし，$\gcd(x,y)$ で $x$ と $y$ の最大公約数を表します．
• $T$ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

• $1\leq T\leq 200$
• $1\leq N\leq 10^9$
• $1\leq A,B,C,D\leq 10^4$
• 入力される数値は全て整数

$N$ の小さいところで愚直解をみると、一見、いかにも「ある周期でループしますよ」みたいな法則がありそうに見えるが、 実は「ある巨大な周期の中の小周期がそう見えるだけで、$N$ が大きくなると崩れますが？」というケースがあったりする。

（後で判明することだが）この制約では周期は最長で $10^8$ くらいになるので、1周期を全て計算するのは無理。

「一次式ごと、ユークリッドの互除法する」が、解法の第一手。
剰余ってどう定義するの、という疑問があるが、要は以下を利用して

• 整数 $k$ に対し、$\mathrm{GCD}(Ai+B,Ci+D)=\mathrm{GCD}(Ci+D,(A-kC)i+(B-kD))$

$i$ の係数の一方である $C$ を $0$ にすることが目的なので、 $C \neq 0$ の間、$k=\left \lfloor \frac{A}{C} \right \rfloor$ として、 $A←C,B←D,C←A-kC,D←B-kD$ とすればよい。

その結果、元の式は $\mathrm{GCD}(Ai+B,Ci+D)=\mathrm{GCD}(A'i+B',|D'|)$ となり、扱いやすい形になる。

$|D'|=0$ の時、$\mathrm{GCD}(A'i+B',0)=A'i+B'$ なので、$i=1,2,...,N$ の時の総和は簡単に求められる。

$|D'|\neq 0$ とすると、$\mathrm{GCD}(A'i+B',|D'|)$ は、当然、$|D'|$ の約数の値しか取りえない。

各 $i$ について $\mathrm{GCD}(A'i+B',|D'|)$ をズバリ求めるのは難しいが、 「$\mathrm{GCD}(A'i+B',|D'|)$ が $d$ の倍数になるような $1 \le i \le N$ の個数は何個？」 という問題は、高速に解ける。（後述）

全ての $D'$ の約数についてこれがわかれば、約数系包除（約数系メビウス変換）を行うことでズバリの個数も求められる。

• エラトステネスの篩の活用法を総特集！ 〜 高速素因数分解・メビウスの反転公式 〜 #AtCoder - Qiita

各 $d$ につき、GCDがズバリ $d$ となる $i$ の個数が分かったので、答えが求められる。

「全ての $D'$ の約数について」ある値を求めなければいけないが、 そもそも列挙できる規模であることが保証されるの？ということを確認する。

$A',D'$ の値の範囲を確認すると、$A,B,C,D$ の値の上限を $M$（$=10^4$）として、

• $A'$
  • この一次式のユークリッドの互除法の操作は、整数 $A,C$ に対する一般的な互除法とやっていることは同じである。
  • よって、元の値から増えることはないので、$1 \le A' \le M$
• $D'$
  • $AD-BC$ の絶対値は、操作後も $C(B-kD)-D(A-kC)=BC-AD$ となることから、保存される。
  • 最終的な形では、$A'D'-B'\cdot 0=A'D'$ となる。
  • $D'=\frac{\pm(AD-BC)}{A'}$ となることから、$-M^2 \lt D' \lt M^2$

高々 $10^8$ である $|D'|$ の約数の最大個数は、$D'=73513440$ の時の $768$ 個である。

• 高度合成数の一覧 | アルゴ式

• $N,A,B,d$ が与えられる。
• $Ai+B$ が $d$ の倍数になるような $1 \le i \le N$ の個数は何個？

$g=\mathrm{GCD(A,d)}$ として、$B$ が $g$ の倍数でない場合、答えは $0$。

そうでない場合、$A,B,d$ をそれぞれ $g$ で割っても答えは変わらないので割って考える。

拡張ユークリッドの互除法を用いて $Ax \equiv 1 \mod{d}$ である $x$ を見つけると、 $i \equiv -Bx \mod{d}$ となる $i$ が、条件を満たすものである。

正で条件を満たす最小の $i$ を $i_0$ として、$\left \lfloor \dfrac{N-i_0}{d} \right \rfloor +1$ が答え。

Python3

from collections import defaultdict

from atcoder._math import _inv_gcd


def get_primes(n):
    """ nまでの素数リスト """
    candidates = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        candidates.pop()
    candidates[1] = 0
    candidates[2] = 1
    for p in range(3, int(n ** 0.5) + 1, 2):
        if candidates[p]:
            for m in range(p * p, n + 1, 2 * p):
                candidates[m] = 0
    return [p for p, b in enumerate(candidates) if b]


def prime_factorize(x, primes=None):
    """ xを素因数分解、辞書型で返す """
    # primes: sqrt(x)までの素数リスト
    #   省略時は奇数を試し割り（2だけ別処理）
    #   単発なら不要だが、複数のxで行う場合は事前計算した方がよい

    factors = defaultdict(int)
    if primes is None:
        if x & 1 == 0:
            b = (x & -x).bit_length() - 1
            factors[2] = b
            x >>= b
        primes = range(3, x, 2)
    for p in primes:
        if p * p > x:
            break
        if x % p == 0:
            factors[p] = 1
            x //= p
            while x % p == 0:
                factors[p] += 1
                x //= p
    if x != 1:
        factors[x] = 1
    return dict(factors)


def solve(n, a, b, c, d, primes):
    MOD = 998244353

    # 1次式ごとユークリッドの互除法して、c=0 にする
    while c > 0:
        k = a // c
        a -= c * k
        b -= d * k
        a, b, c, d = c, d, a, b
    d = abs(d)

    if d == 0:
        ans = a * (n * (n + 1) // 2) + b * n
        ans %= MOD
        return ans

    def sub(a, b, k):
        """ 1<=i<=n で、ai+b が k の倍数になる回数 """
        g, x = _inv_gcd(a, k)
        if b % g != 0:
            return 0
        a //= g
        b //= g
        k //= g
        x *= -b
        x %= k
        if x == 0:
            x += k
        if n < x:
            return 0
        return (n - x) // k + 1

    pf = prime_factorize(d, primes)
    divisors = [1]
    for p, cnt in pf.items():
        size = len(divisors)
        for j in range(1, cnt + 1):
            q = p ** j
            for i in range(size):
                divisors.append(divisors[i] * q)
    divisors.sort()
    mapping = {div: i for i, div in enumerate(divisors)}

    result = [sub(a, b, div) for div in divisors]

    for p in pf.keys():
        for i, div in enumerate(divisors):
            if div * p in mapping:
                j = mapping[div * p]
                result[i] -= result[j]

    ans = 0
    for i in range(len(result)):
        ans += result[i] * divisors[i]
        ans %= MOD
    return ans


def check():
    from math import gcd
    def naive(n, a, b, c, d):
        ans = 0
        for i in range(1, n + 1):
            ans += gcd(a * i + b, c * i + d)
        ans %= 998244353
        return ans

    PRIMES = get_primes(10000)
    n = 10000
    cand = (1, 2, 500, 999, 1000)
    for a in cand:
        for b in cand:
            for c in cand:
                for d in cand:
                    ans1 = solve(n, a, b, c, d, PRIMES)
                    ans2 = naive(n, a, b, c, d)
                    if ans1 == ans2:
                        continue
                    print(f'==== NG ====')
                    print(f'{n} {a} {b} {c} {d}')
                    print(f'{ans1=} {ans2=}')
    print('FINISH')


check()


def main():
    PRIMES = get_primes(10000)

    t = int(input())
    for _ in range(t):
        n, a, b, c, d = map(int, input().split())
        ans = solve(n, a, b, c, d, PRIMES)
        print(ans)


if __name__ == '__main__':
    main()

B - Two-Powered Sum

• 正整数 $N$ と素数 $P$ が与えられます．
• すべての要素が $0$ である長さ $N$ の数列 $A=(A_1,A_2,\ldots,A_N)$ があります．
• あなたは以下の操作を $0$ 回以上好きな回数繰り返すことができます．
  • 非空な $\lbrace 1,2,\ldots,N\rbrace$ の部分集合 $S$ を選ぶ．$\displaystyle x=\sum_{i\in S}2^{i-1}$ として，各 $i\in S$ に対して $A_i$ を $x$ で置き換える．

• 操作を繰り返すことで最終的に得られる $A$ としてあり得るものの個数を $P$ で割った余りを求めてください．

• $1\leq N\leq 700$
• $P$ は $10^8\lt P\lt 10^9$ を満たす素数
• 入力される数値は全て整数

$x$ は「どの要素集合を1回の操作で選びましたか」を指すユニークな値となる。

S={1,2,5}  ↔  x=10011
S={3,4}    ↔  x=01100

なので、以下はわかりやすいよう、$x$ もそのまま集合として表す。つまり、

• $A$ は数列でなく、“集合”の列と扱い、初期状態は全て $A_i=\phi$（空集合）
• 各操作は、「$S$ を決め、$S$ に含まれる各 $i$ について $A_i=S$ とする」ことに相当する。

また、操作を逆から考える。

• 最後に行った操作については、例えば $S=\{1,2,5\}$ なら、最終的な $A_1,A_2,A_5$ は全て $S$ となっているはずである。
• 最後から2番目以前は、（完全に後から上書きされるだけの無駄な操作を除けば）1つ以上の新規要素と、0個以上の既に選んだ要素から選んで $S$ とし、新規要素のみ $A_i=S$ とすることに相当する。

操作 $0$ 回のものも含め、以上の操作によって形成される全ての $A$ を数え上げればよい。

ここで悩ましいのは、「どちらを先にしても、結果的にできる $A$ が同じとなる操作」が存在する点である。

       1 2 3 4 5
1回目    o o
2回目  o   o      ←┬どちらを先にしても変わらない
3回目    o   o    ←┘  {1,3} {2,3} {2,3} {2,4} {}

入れ替え可能な操作は、操作列において隣接しているとは限らない。

       1 2 3 4 5
1回目    o o
2回目  o   o      ←┐3回目は、必ず2回目の後でないといけないが、
3回目  o       o    │
4回目    o   o    ←┴2回目と4回目は、どちらを先にしても変わらない

操作の順番は、以下の依存関係として表せる。（まぁ、意味するところを考えると当たり前ではある）

• 各操作の $S$ を「新規要素 $P$」と「既存要素 $Q$」に分けて考える。
• 2つの操作 $i,j$ で、ある要素 $x$ を、$i$ は $P$ として、$j$ は $Q$ として含むなら、$i$ は $j$ より先に操作していないといけない。

操作の $(P,Q)$ の選び方を頂点ラベル、依存関係を $i→j$ の有向辺として、 ラベルを含むグラフの構造が同じ操作列からは、同じ $A$ ができる。

       1 2 3 4 5                           ①
1回目    o o      ① P:{2,3}  Q:{}        ↙↘    ①→②→③→④と操作しても
2回目  o   o      ② P:{1}    Q:{3}      ②  ④   ①→②→④→③と操作しても
3回目  o       o  ③ P:{5}    Q:{1}      ↓       ①→④→②→③と操作しても
4回目    o   o    ④ P:{4}    Q:{2}      ③       同じ A ができる

このようなDAGを重複無く数え上げるには、トポロジカルソートした時に、 始点（流入辺の無い頂点）からの距離毎に決めるDPが考えられる。

  ○  ○  ○    ←始点からの距離0: レイヤー0
  ↓↙↓↘
  ○  ○  ○    ←始点からの距離1: レイヤー1
    ↙↓×↓
  ○  ○  ○    ←始点からの距離2: レイヤー2

レイヤー $i$ は、必ず、レイヤー $i-1$ と依存関係がある。でなければもっと上のレイヤーにできたはずなので。
つまり、前のレイヤーで $P$ として選ばれた要素の少なくとも1つを、$Q$ として含む。

レイヤー毎に、そのレイヤーに配置する頂点の個数と具体的な $P,Q$ の内容、つまり以下のような内容

• そのレイヤーで $P$ として新規採用する要素数およびその選び方、各頂点への要素の振り分け方
• $Q$ の内容（直前およびさらに前のレイヤー頂点との依存関係の張り方）

のパターン数を考慮していけばよい。

• $\mathrm{DP}[i,j]:=i$ 個の要素を $P$ として採用済みで、特に最後のレイヤーに配置した頂点の $P$ の要素数の合計が $j$ 個であるようなグラフの個数

ここで、レイヤー数は関係ない点に注意。グラフのレイヤー数が異なっても $i,j$ が同じグラフからは同じ遷移が可能である。

これの遷移を考える。素直に考えると、

• $i=1,2,...,N$: 全体採用済みの要素数ごとに、
  • $j=1,2,...,i$: その中で最後のレイヤーの要素数について場合分けして、
    • $k=1,2,...,N-i$: 新たにこのレイヤーで $P$ として採用する個数を決め、
      • $l=1,2,...,k$: それをいくつの頂点に分けるか決める

4重ループとなってしまう。いくらか定数倍で削減されるとは言え、$N=700$ はさすがに無理。

…ではあるが、ひとまず遷移の式を考える。

各レイヤーでは、$k$ 個の要素を、何個の頂点（$l$ 個）に振り分けるかによって、遷移係数に違いが生じる。

$k$ 個の要素を $l$ 個の非空な集合にわける方法は、スターリング数 $Str(k,l)$ として求められる。 特に「集合自体の順序」「集合の中での各要素の順序」を区別しない場合は、第2種スターリング数が当てはまる。 よって、$Str(N,N)$ までを $O(N^2)$ で前計算しておく。

• スターリング数

現在のレイヤーに配置する $l$ 個の頂点に対し、$Q$ の選び方は全て共通で、1頂点当たり以下のパターンがある。

• 直前レイヤーから1つは選ばなければならない。$2^{j}-1$
• それ以外のレイヤーからは好きに選んでよい。$2^{i-j}$

以上より、$i,j,k$ を決めたときの遷移は以下になる。

• 1頂点当たりの $Q$ の選び方を $W_{i,j}=(2^{j}-1)2^{i-j}$ とする。
• $\displaystyle \mathrm{DP}[i+k,k]+=\mathrm{DP}[i,j] \times {}_{N-i}C_{k} \times \sum_{l=1}^{k} Str(k,l) W_{i,j}^l$

この式は、$(i,j,l)$ に依存する部分と、$(i,k,l)$ に依存する部分に綺麗に分けられる。

• 上記の式の順序を入れ替えると、
• $\displaystyle \mathrm{DP}[i+k,k]+= {}_{N-i}C_{k} \sum_{l=1}^{k} Str(k,l) \times (\mathrm{DP}[i,j] W_{i,j}^l)$

前半の括弧外は $j$ に依存せず、後半の括弧内は $k$ に依存しない。

よって、$i,j$ を決めた段階で、$k$ のループ前に $l$ 毎に結果を分けて前計算しておける。

• $i=1,2,...,N$: 全体採用済み要素数の昇順に、
  • $j=1,2,...,i$: その中で最後のレイヤーの要素数について場合分けして、
    • $l=1,2,...,N-i$: いくつの頂点を配置するか毎に前計算する。
  • $k=1,2,...,N-i$: 新たにこのレイヤーで $P$ として採用する個数を決め、
    • $l=1,2,...,k$: 前計算結果を利用しつつ、遷移させる

このようにして、$O(N^3)$ に削減できる。

それでも $700^3=3.43 \times 10^8$ なので下手な実装をすると厳しいが、 添字の範囲から定数倍で $\frac{1}{3}$ 程度になること、演算が単純なことなどで、意外と間に合う。

Python3

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


def solve(n, p):
    stirling = [[0] * (n + 1) for _ in range(n + 1)]
    stirling[0][0] = 1
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            stirling[i][j] = (stirling[i - 1][j - 1] + j * stirling[i - 1][j]) % p

    facts, finvs = precompute_factorials(n, p)

    def ncr(n, r):
        return facts[n] * finvs[r] % p * finvs[n - r] % p

    POW2 = [1]
    for i in range(n):
        POW2.append(POW2[-1] * 2 % p)

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        dp[i][i] = sum(stirling[i]) % p * ncr(n, i) % p

    precalc = [0] * (n + 1)
    for selected in range(1, n):
        remaining = n - selected
        for i in range(1, remaining + 1):
            precalc[i] = 0
        for selected_just_before in range(1, selected + 1):
            if dp[selected][selected_just_before] == 0:
                continue
            pattern1 = (POW2[selected_just_before] - 1) * POW2[selected - selected_just_before] % p
            w = dp[selected][selected_just_before] * pattern1 % p
            for group_count in range(1, remaining + 1):
                precalc[group_count] += w
                precalc[group_count] %= p
                w *= pattern1
                w %= p
        for select_current in range(1, remaining + 1):
            tmp = 0
            for group_count in range(1, select_current + 1):
                tmp += stirling[select_current][group_count] * precalc[group_count]
                tmp %= p
            tmp *= ncr(remaining, select_current)
            dp[selected + select_current][select_current] += tmp
            dp[selected + select_current][select_current] %= p

    ans = sum(sum(row) for row in dp) % p
    return ans


n, p = list(map(int, input().split()))
ans = solve(n, p)
print(ans)

D - Two Balanced Subtrees

• 正整数 $N$ が与えられます．
• 頂点数が $2^N-1$ の完全二分木があります．
  • 頂点には $1$ から $2^N-1$ までの番号が付いています．
  • 頂点 $1$ が根であり，各 $i\ (1\leq i\lt 2^{N-1})$ について，頂点 $i$ は頂点 $2i$ と頂点 $2i+1$ を子として持ちます．
• 各頂点に $1$ 以上 $2^N-1$ 以下の相異なる整数を書き込む方法であって，以下の条件を満たすようなものを一つ求めてください．
  • 各 $i\ (1\leq i\lt 2^{N-1})$ について，頂点 $2i$ を根とする部分木の各頂点に書かれた整数の総和と，頂点 $2i+1$ を根とする部分木の各頂点に書かれた整数の総和の差の絶対値は $1$ である．
• この問題の制約下で条件を満たす整数の書き込み方が必ず存在することが証明できます．

• $2\leq N\leq 18$
• 入力される数値は全て整数

こういうの、手元なり全探索なりで小さいケースから法則性を見つける、という以外に解き筋が分からないが、 「全探索範囲が大きすぎて $N$ を大きくできない（小さすぎると法則性も何も分からない）」 「全探索解が多すぎて、その中から法則性のある1つを見つけるのが難しい」 というケースにどう対応したものか、いつも悩む。

兄弟の値とそれ以下が決まれば自身の値は2通りになるので、 全探索は葉から埋めていけばざっくり $O(2^N!!2^{N/2})$ 程度となる。 置けなくなったら早期リターンをしても、$N=4$ が限度で、$N \ge 5$ は厳しい。

以下の法則は見つかるが、探索範囲を絞るのには弱い。

• 兄弟要素 $u,v$ の値の偶奇は必ず異なる
  • ある $v$ の部分木について、左右の子の部分木の総和は1だけ異なるので、その和は奇数。
  • $u+奇数$ と $v+奇数$ がちょうど1だけ異なるので、$u,v$ の値の偶奇は必ず異なる
• 頂点1の値は必ず奇数
  • 根以外の全ての兄弟間で、偶数と奇数は1個ずつ消費される。$1～2^N-1$ では奇数の方が1個多い。

$N=4$ の全探索解でも数がそれなりにあるので全て見ていくのはしんどい。
ある程度対称性・法則性をもった解があると信じて、「ではその対称性とは何だろう」と当たりを付け、

• 中央で鏡映しにした時に対応する頂点同士の値の和が、根以外の全ての頂点で一定

という条件で絞り込むと、以下の解が見つかる。

               1
       2              15
   3       8       9      14
13  12  11  10   7   6   5   4

• 根以外で、鏡写しの頂点との和が全て $17$
• 頂点1から、左下に $1,2,3$ と小さい方から、右下には $15,14$ と大きい方から配置されていて、何となく法則性がある。
• 最下段のみ並びが逆転しているが、ひっくり返せば左半分に $2～8$ が、右半分に $9～15$ が揃っている

さすがにこれが当たりかな、と思うが、小さすぎてまだ完全に法則性に確信が持てない。

それっぽい法則を保ちながら、$N=5$ を手動で構築すると、

                               1
               2                              31
       3              16              17              30
   4       9      10      15      18      23      24      29
28  27  26  25  22  21  20  19  14  13  12  11   8   7   6   5

鏡写しの頂点との和は全て $33$ となっている。$N=4$ の時と合わせて考えると、$2^N+1$ になればいいっぽい。
また最下段の並びが反転しているため少し分かりづらいが、反転を戻して

N=4 の最下段を反転
               1
       2              15
   3       8       9      14
 4   5   6   7  10  11  12  13

N=5 の最下段を反転した上での左半分
               2
       3              16
   4       9      10      15
 5   6   7   8  11  12  13  14

全ての頂点に一律+1されており、フラクタル構造があることが分かる。
左半分を構築できれば右半分の値も、鏡写しの和から算出できる。
$N=1$ から再帰的に構築し、最後に最下段を反転させれば、$O(2^N)$ で答えが求められる。

説明の内容を具体例で確認しやすくするため、改めて $N=4,5$ の答えを再掲する。

N=4            1
       2              15
   3       8       9      14
13  12  11  10   7   6   5   4

N=5                            1
               2                              31
       3              16              17              30
   4       9      10      15      18      23      24      29
28  27  26  25  22  21  20  19  14  13  12  11   8   7   6   5

成立している解に対し、「特定の段の全ての要素に一定値を加算」しても、「左右の部分木の重みの差が1」という状態は崩れない。 加算された段については兄弟にも同じ値が加算されているし、親に関しても、親の兄弟同士での加算値は等しいので。

解法で示した構築方法では、$N$ の解の左半分は、$N-1$ の解に以下を加算している。

• 最下段以外は $1$、（$2^{N-2}-1$ 個）
• 最下段は $2^{N-1}-1$、（$2^{N-2}$ 個）

右半分は、$N-1$ の解に以下を加算している。

• 最上段は $2^{N}-2$、（$1$ 個）
• 最上・最下段以外は $2^{N-1}-1$、（$2^{N-2}-2$ 個）
• 最下段は $1$、（$2^{N-2}$ 個）

左の最下段や、右の最上・最下段以外の加算値 $2^{N-1}-1$ が少し非自明だが、 $N-1$ の解も $N-2$ から同様に構築されたものであり、 自身と「左半分の中での鏡写し（$N=5$ における $4$ に対しての $15$ の位置）」との和が、$N-1$ の解では $2^{N-1}+1$ であったことを経由することで導ける。

左右それぞれの中では、同じ段には同じ値を加算しているので、 上から3段目以降については、兄弟との重みの差が1という状態が $N-1$ から引き継がれて成り立っている。
新たに兄弟が生じた2段目についても、 左右で個数と加算値をかけて足し合わせると、左が $2^{2N-3}-1$、右が $2^{2N-3}$ となり、 やはり重みの差は $1$ だけ異なることがわかる。

また、使われる値の範囲についても、（説明の簡略化のため、最下段のみ左右を入れ替えて）

• 左半分は、$N-1$ の解に全て $+1$ しているので、$2～2^{N-1}$
• 右半分は、$2^N+1$ から左半分を引いた値なので、$2^{N-1}+1～2^N-1$
• 根に $1$ を配置

となり、$1～2^{N}-1$ が被らず使われていることが分かる。

Python3

def solve(n):
    def sub(n):
        if n == 1:
            return [0, 1]
        sub_result = sub(n - 1)
        result = [0] * (1 << n)
        result[1] = 1
        value_mirror = (1 << n) + 1
        for i in range(1, 1 << (n - 1)):
            layer_size = 1 << (i.bit_length() - 1)
            index_mirror = layer_size * 6 - 1
            j = i + layer_size
            result[j] = sub_result[i] + 1
            result[index_mirror - j] = value_mirror - sub_result[i] - 1
        return result

    ans = sub(n)
    ans[1 << (n - 1):1 << n] = reversed(ans[1 << (n - 1):1 << n])
    return ans[1:]


def verify(n, ans):
    n2 = 1 << n
    assert len(ans) == n2 - 1
    appeared = [False] * n2
    appeared[0] = True
    for p in ans:
        appeared[p] = True
    assert all(appeared)

    weights = [0] * n2
    for i in range(n2 >> 1, n2):
        weights[i] = ans[i - 1]
    for i in range((n2 >> 1) - 1, 0, -1):
        l = i << 1
        r = l + 1
        weights[i] = weights[l] + weights[r] + ans[i - 1]

    for i in range(2, n2, 2):
        assert abs(weights[i] - weights[i + 1]) == 1

    print('OK')


n = int(input())
ans = solve(n)
print(*ans)