AtCoder Regular Contest 227 A,B,C,D,E 問題メモ

AtCoder Regular Contest 227

CDEが700点3連続構成。時間があればどれかは解けると思ったんだけどなぁ。

A - Fermat Point of Binary Strings

• 長さ $2N$ で、0 と 1 をそれぞれ $N$ 個含む文字列をよい文字列と呼びます。
• よい文字列 $S, T$ に対して、$S$ の隣り合う $2$ 文字を入れ替える操作を $0$ 回以上行って$T$ に一致させるために必要な操作回数の最小値を $\operatorname{dist}(S, T)$ とします。
• よい文字列 $A, B, C$ が与えられます。すべてのよい文字列 $X$ のうち、
• \[\operatorname{dist}(A, X)+\operatorname{dist}(B, X)+\operatorname{dist}(C, X)\]
• の値を最小にするものを $1$ つ求め、その最小値とともに出力してください。

• $1 \le N \le 2 \times 10^5$
• $A, B, C$ はそれぞれ長さ $2N$ のよい文字列
• $N$ は整数

$dist(S,T)$ を求めるのにやることは明らかで、$i=1,2,...,N$ 個目の 1 の出現位置の差を取り、合計すればいい。

S  0 1 0 0 1 1 1 0
   ,-' ,---' | `-,
T  1 0 1 0 0 1 0 1

$S$ 側が $A,B,C$ の3通りになった時も、$i$ 毎に独立に考えていい。

$A,B,C$ における $i$ 個目の 1 の出現位置をそれぞれ $p_a,p_b,p_c$ とする。 $f(x)=|p_a-x|+|p_b-x|+|p_c-x|$ を最小化するには、3つの中で2番目に大きい値を $x$ とするとよい。

∵それより増やすと、1増やすごとに1個以下との距離が1近づき、2個以上との距離が1離れるので、必ず $f(x)$ は大きくなる。 減らす場合も同様。

各 $i$ について最小化する $x$ を求め、それを $D$ における $i$ 個目の 1 の位置とすればよい。

Python3

def solve(n, a, b, c):
    pos = [[] for _ in range(n)]
    cnt = [0, 0, 0]
    for i in range(n * 2):
        if a[i] == '1':
            pos[cnt[0]].append(i)
            cnt[0] += 1
        if b[i] == '1':
            pos[cnt[1]].append(i)
            cnt[1] += 1
        if c[i] == '1':
            pos[cnt[2]].append(i)
            cnt[2] += 1
    ans = ['0'] * (n * 2)
    dist = 0
    for i in range(n):
        pos[i].sort()
        x = pos[i][1]
        ans[x] = '1'
        dist += sum(abs(x - pos[i][j]) for j in range(3))
    ans = ''.join(ans)
    return dist, ans


n = int(input())
a = input()
b = input()
c = input()
dist, ans = solve(n, a, b, c)
print(dist)
print(ans)

B - Know Your Place

• 長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
• $A$ の要素を並べ替えて得られる数列 $B=(B_1,B_2,\ldots,B_N)$ であって、すべての$i=1,2,\ldots,N$ について次の条件を満たすものが存在するか判定し、存在する場合はそのような数列を $1$ つ構成してください。
  • $B_i$ は、$1\le j\lt i$ かつ $B_j\lt B_i$ を満たす整数 $j$ の個数に等しい。

• $1\le N\le 5\times 10^5$
• $0\le A_i\lt N$
• 入力される数値はすべて整数

$A$ は一旦無視して（あらゆる値があることにして）、$B$ で各 index に置くことができる値で樹形図を書いてみる。

i 0   1   2   3
  0---0---0---0 ...
  |   |   `---3
  |   `---2---0
  |       |---2
  |       `---3 
  `---1---0---0
      |   `---3
      |---1---0
      |   |---1
      |   `---3
      `---2---0
          |---1
          |---2
          `---3

これを元に観察と考察をすると、index $i$ には

• $i$ より大きい値は置けない。（左にある数の個数がそもそも足りないので当然）
• $i$ はいつでも置ける。（左には $i$ 個の数があり、1つ上の条件より、それらは全て $i$ 未満の数なので）
• $i$ 未満の数 $a$ は、「index $[a, i)$ の範囲には、$a$ 未満の数を置いていない」ときに置ける。
  • （index $a$ より左にあるのは必ず $a$ 未満の数で、それだけで $a$ 個あるので、そこから増えてはいけない）

よって、「置ける中で最も大きい数から置いていく」以下の解法が成り立つ。

• 大きい方から取り出すヒープキュー $Q$ を用意する。
• $i=0,1,...,N-1$ の順に、以下を行う
  • $Q$ に $i$ を、$A$ に出現する個数だけ追加する
  • $B_i=Q.pop()$ とする。$Q$ がこの時点で空なら不可能

Python3

from collections import Counter
from heapq import heappush, heappop


def solve(n, aaa):
    cnt = Counter(aaa)
    ans = []
    hq = []
    for i in range(n):
        for k in range(cnt[i]):
            heappush(hq, -i)
        if len(hq) == 0:
            return None
        ans.append(-heappop(hq))
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
if ans is None:
    print('No')
else:
    print('Yes')
    print(*ans)

C - Follow the Letters

• 英小文字からなる長さ $N$ の文字列 $S$ が与えられます。$S$ の $i$ 文字目を $S_i$ とします。
• $N$ 個の島が円環状に並んでおり、時計回りに島 $1$、島 $2$、$\ldots$、島 $N$ の順で番号が付けられています。特に、島 $N$ の時計回りの隣の島は島 $1$ です。島 $i$ には文字 $S_i$ が書かれています。はじめ、それぞれの島には人が $1$ 人ずついます。
• あなたは次の操作を $0$ 回以上行うことができます。
  • $S$ に含まれる文字 $c$ を $1$ つ選ぶ。
  • すべての人はそれぞれ現在いる島を出発し、時計回りに島を $1$ 個ずつ移動する。出発後に文字 $c$ が書かれた島に初めて到着した時点で止まる。現在いる島に文字 $c$ が書かれている場合でも出発する。

• 操作をすべて終えた後に人が $1$ 人以上いる島の個数としてあり得る最小値を $K$ とします。
• $K$ と、操作後に人が $1$ 人以上いる島の個数を $K$ にする操作列を求めてください。
• なお、この問題の制約の下で、操作後に人が $1$ 人以上いる島の個数を $K$ にする長さ $10^6$ 以下の操作列が必ず存在することが証明できます。

• $1 \le N \le 1000$
• $S$ は英小文字からなる長さ $N$ の文字列
• $N$ は整数

考察と実装に分けると考察がほぼ全ての問題。未証明でも勘でワンチャン通せそう。

$S$ の最小周期を $p$ とする。 つまり abcdabcdabcd は周期 4 を持つように、$p'$ 文字転回シフトしたら元の $S$ と一致するとするような $p'$のうち、$p$ は最小のものを指すとする。

この時、周期の同じ位置にいる人は、どのように $c$ を選ぼうと常に $p$ だけ離れた位置関係を保ち続け、合流することはない。 さっきの例では、$1,5,9$ 番目の a にいる人は、必ず $4$ だけ離れた位置関係を保ち続ける。

よって、$K$ は $\frac{N}{p}$ 未満にはならない。

逆に、$\frac{N}{p}$ は必ず達成できる。

一例として、$S[1:p]=S_1,S_2,...,S_{p}$ を順に宣言したとする。
この時、島 $p$ に居た人は、距離 $p$ だけ動いて島 $2p$ に移動している。

一方、島 $1～p-1$ に居た人は、必ず $p+1$ 以上の距離を動いている。
もし $1 \le i \le p-1$ からの移動で、島 $p$ の人と同じく距離 $p$ しか移動していない場合、 $S[1:p] = S[i+1:p+i]$ となっていることになる。しかし、これは $p$ が最小周期であることと矛盾する。

よって、$1～p-1$ にいた人たちは $p$ より多く移動している。 これを繰り返すことで、最初 $1～p-1$ にいた人たちはいつかは最初 $p$ にいた人に追いつき、以降は同じ移動となる。

$S[1:p]$ 1回で少なくとも距離 $1$ は追いつけるので、 つまり、$S[1:p]$ を $p-1$ 回繰り返した文字列が答えの1つとなる。

最小周期 $p$ および最適な $K$ は、Z-algorithm 等を使って求めることができる。

• $S+S$ に Z-algorithm を適用し、$1 \le i \le N$ のうち $z[i] \ge N$ となるものの個数が $K$

Python3

from atcoder.string import z_algorithm


def solve(n, s):
    z = z_algorithm(s + s)
    k = sum(z[i] >= n for i in range(n))
    return k, s * n


n = int(input())
s = input()
k, ans = solve(n, s)
print(k)
print(len(ans))
print(ans)

「最小操作回数」を達成する一例を構築せよ、という問題でも解くことができる。

$K \ge 2$ の場合、1周期分を取り出し（$T←S[1:p]$）、$T$ 上で人を1点に集める問題としても元の問題の答えと一致する。 つまり、全てのケースは $K=1$ に帰着できる。

操作を末尾から考える。

最適な操作列において、最終的に島 $z$ に集められたとする。 最終操作の宣言文字は明らかに $S_{z}$ であり、 さらに文字の並びから「最終操作直前に $[l,r)$ の範囲にいたら、実際に最終操作で島 $z$ に集められる」という、 円環状の区間 $[l,r)$ も、逆算で求められる。

さらに1つ前の操作を考えていく。ある区間 $[l,r)$ に対し、「$[l,r)$ に包含される区間に移動させられるような、宣言文字と操作前にいる位置範囲」を求めたい。

• 宣言文字は、その区間内にある文字に限られる
• 文字 $c$ ごとに、「操作直前に $[l',r')$ の範囲にいたら、実際にこの操作で $[l,r)$ に包含される範囲に集められる」という区間 $[l',r')$ が逆算で求められる。

で、この区間が $N$ 全体を覆うようになればゴール。

最終的に集める島 $z$ を固定した時、 そこに何回かの操作で到達可能である初期位置の範囲は必ず（円環状の）区間になる、という点がポイント。 $(l,r)$ の組を1頂点と見なし、 最終的に集める位置 $z$ を全て試す多始点BFSで、$O(\sigma N^2)$ で求められる。（$\sigma$ は文字種数）

Python3

from collections import deque

from atcoder.string import z_algorithm


def solve(n, s):
    z = z_algorithm(s + s)
    k = sum(z[i] >= n for i in range(n))
    p = n // k
    if p == 1:
        return k, ''
    t = s[:p]
    chars = sorted(set(t))

    # prev_leq[c][i]: i 以前(i含む)の最後の c 出現への後退距離 (0..p-1)
    # prev_strict[c][i] = prev_leq[c][i-1] + 1
    prev_leq = {}
    for c in chars:
        dist = [0] * p
        last = -1
        for i in range(2 * p):
            if t[i % p] == c:
                last = i
            if i >= p:
                dist[i % p] = i - last
        prev_leq[c] = dist

    # 状態 (l, len): 「最終合流点に到達する開始位置の区間」 len は 1..p-1、len>=p でゴール
    INF = -1
    bfs_dist = [[INF] * p for _ in range(p)]  # [l][len-1]
    par = {}
    dq = deque()
    for q in range(p):
        bfs_dist[q][0] = 0
        dq.append((q, 1))
    goal = None
    while goal is None:
        l, ln = dq.popleft()
        d0 = bfs_dist[l][ln - 1]
        r = (l + ln - 1) % p
        for c in chars:
            dz = prev_leq[c][r]
            if dz > ln - 1:
                continue  # 区間内に c が無い
            dw = prev_leq[c][(l - 1) % p] + 1
            nln = ln + dw - dz - 1
            if nln >= p:
                goal = (l, ln, c)
                break
            nl = (l - dw) % p
            if bfs_dist[nl][nln - 1] == INF:
                bfs_dist[nl][nln - 1] = d0 + 1
                par[nl, nln] = (l, ln, c)
                dq.append((nl, nln))

    l, ln, c = goal
    ops = [c]
    while bfs_dist[l][ln - 1] > 0:
        l, ln, c = par[l, ln]
        ops.append(c)
    return k, ''.join(ops)


n = int(input())
s = input()
k, ans = solve(n, s)
print(k)
print(len(ans))
print(ans)

D - Median of Binary Strings

• 0 と 1 からなる長さ $M$ の文字列 $S_1,S_2,\ldots,S_N$ が与えられます。
• はじめ、黒板には $S_1,S_2,\ldots,S_N$ が書かれています。
• あなたは次の操作を $0$ 回以上行うことができます。
  • 黒板に書かれている文字列から、同じ文字列を複数回選んでもよいものとして $3$ つ選び、それぞれ $A,B,C$ とする。
  • 次の条件を満たす長さ $M$ の文字列 $D$ を新たに黒板に書く。
    • $i=1,2,\ldots,M$ のそれぞれについて、$A,B,C,D$ の $i$ 文字目をそれぞれ $A_i,B_i,C_i,D_i$ としたとき、$D_i$ は $A_i,B_i,C_i$ のうち少なくとも $2$ つと等しい。

• $Q$ 個の文字列 $T_1,T_2,\ldots,T_Q$ が与えられます。
• $i=1,2,\ldots,Q$ のそれぞれについて、はじめの状態から操作を行うことで、$T_i$ が黒板に書かれている状態にできるか判定してください。

• $1 \leq N \leq 500$
• $1 \leq M \leq 500$
• $1 \leq Q \leq 500$
• $S_i$ は 0 と 1 からなる長さ $M$ の文字列 $(1 \leq i \leq N)$
• $T_i$ は 0 と 1 からなる長さ $M$ の文字列 $(1 \leq i \leq Q)$
• 入力される数値はすべて整数

同じ文字列を選んでもよいという設定だが、意味は無い。 3つのうち2つでも同じ文字列 $S_i$ を選んだら、$D$ も必然的に $S_i$ になり、新規文字列は増えない。
$A,B,C$ は、別々の文字列を選ぶと考えてよい。

実験してみると、$N=4～5$ などでは意外と新規文字列を増やせない。
$N$ を増やせばできる文字列は増えていき、$M=4,N=12$ などで $S$ の初期値を変えて試してみれば、 （長さ4の01文字列は16個なので）大体の場合で残り4つの文字列は作れるようになる。 しかし、それでも以下のようなケースでは増えない。

0000  0100  1000
0001  0101  1001
0010  0110  1010
0011  0111  1011

例えばこの 1011 を 1101 なんかにすると、途端に $16$ 個全ての文字を作れるようになる。
他にも、以下のケースでも増えない。

0000  0100  1000  1100
0001  0101  1001  1101
            1010  1110
            1011  1111

共通点を探ると、 1つめのケースは「上2桁が'11'のものが存在しない」、 2つめのケースは「1,3桁目が'0,1'のものが存在しない」となっている。

ここで、「ある2つの桁 $i,j$ について、出現していない組は作れない？」とエスパーできる。

例えば「$1$ 桁目が $0$、$3$ 桁目が $1$」の $T$ を作りたいのであれば、 $S$ の中に同じく「$1$ 桁目が $0$、$3$ 桁目が $1$」の文字列が1つは含まれていないといけない。 この条件が、全ての $(i,j)$（$1 \le i \lt j \le M$）で満たされていれば、その $T$ は作れると判定できる？

• 解説 - AtCoder Regular Contest 227

ある桁に対して、$S,T$ の全ての文字列の 01 を一斉に反転させても、できるできないの判定は変わらない。
よって、$T=111...1$ の場合について示せればよい。

これは意外と簡単で、$i$ 桁目と $j$ 桁目がともに 1 である文字列を作るためには、 3個中2個は $i$ 桁目が1の文字列、3個中2個は $j$ 桁目が1の文字列を採用しないといけない。 必然的に、1個は両方が 1 である文字列が必要となってしまう。よって $S$ にない状態では作ることができない。

一方、それが全ての $(i,j)$ で満たされていれば作ることができることも示す。

上2桁が 11 の文字列は前提より既にある。上3桁が 111 である文字列が $S$ に無いとき、 「1,2桁目が11」「1,3桁目が11」「2,3桁目が11」の文字列はそれぞれ存在するので、これらを合わせると 111 が作れる。

次、上4桁が 1111 の文字列を作る。 さっき作った 111? と同様の手順で、1?11 や 11?1 など、4個中3個が 1 の文字列を作ることができる。 これらを合わせると、作ることができる。

以降、$i$ 桁が 1 の文字列は、$i-1$ 個が 1 の文字列3つから再帰的に作ることができる。

このようにして希望の文字列を作ることができる。

Python3

def solve(n, m, q, sss, ttt):
    def lack_pair(sss):
        exists = [[[[0, 0], [0, 0]] for j in range(m)] for i in range(m)]
        for i in range(m):
            for j in range(i + 1, m):
                for s in sss:
                    exists[i][j][s[i]][s[j]] = 1
        return exists

    def judge(t, exists):
        for i in range(m):
            for j in range(i + 1, m):
                if exists[i][j][t[i]][t[j]] == 0:
                    return False
        return True

    if m == 1:
        sss_set = set(sss)
        buf = [t in sss_set for t in ttt]
        return buf

    sss = [list(map(int, s)) for s in set(sss)]
    ttt = [list(map(int, t)) for t in ttt]
    exists = lack_pair(sss)
    buf = [judge(t, exists) for t in ttt]
    return buf


n, m, q = list(map(int, input().split()))
sss = [input() for _ in range(n)]
ttt = [input() for _ in range(q)]
ans = solve(n, m, q, sss, ttt)
print('\n'.join('Yes' if a else 'No' for a in ans))

E - Shift and XOR Switches

• $0$ と $1$ からなる長さ $N$ の数列 $B=(B_1,B_2,\ldots,B_N)$ があります。
• はじめ、$B_1=1$ であり、それ以外の要素は $0$ です。
• $M$ 個のスイッチがあり、スイッチ $i$ ($1 \le i \le M$) には整数 $A_i$ が書かれています。
• スイッチ $i$ を押すと、操作を行う直前の状態を用いて、$1 \le j \le N$ を満たすすべての整数 $j$ について $B_j$ を同時に次のように変更します。
  • \[B_j \leftarrow\begin{cases}B_j \oplus B_{j-A_i} & (A_i \lt j),\\B_j & (j \le A_i)\end{cases}\]
• 各スイッチは $0$ 回または $1$ 回押すことができ、スイッチを押す順番は自由です。
• 最終的な列 $B$ としてあり得るものの個数を $998244353$ で割った余りを求めてください。

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le A_i \lt N$ ($1 \le i \le M$)
• 入力される数値はすべて整数

以下、$B$ のindex を $0,...,N-1$ に捉えなおす。

（愚直コードなどで実験して気付けたが）スイッチを押すことによる操作は、 「ナップサック問題で、重さ $A_i$ の荷物を追加する」行為とよく似ている。演算が max でなく xor だが。

更に言い換えると、以下の形式的冪級数として考えられる。

• $(A_{i1},...,A_{ik})$ を選んだときの $B$ は、係数が mod 2 の世界で、以下の多項式として表現できる
• $\displaystyle \prod_{j=1}^{k} (1+x^{A_{i_j}}) \bmod{x^N}$

実際、$A_i=1$ のスイッチを繰り返し押すと、シェルピンスキーのギャスケットが現れる。パスカルの三角形 mod 2 もこの形になることでも知られる。

操作列    B
()       (1 0 0 0 0 0 0 0 0 0)
(1)      (1 1 0 0 0 0 0 0 0 0)
(1)*2    (1 0 1 0 0 0 0 0 0 0)
(1)*3    (1 1 1 1 0 0 0 0 0 0)
(1)*4    (1 0 0 0 1 0 0 0 0 0)
(1)*5    (1 1 0 0 1 1 0 0 0 0)
(1)*6    (1 0 1 0 1 0 1 0 0 0)
(1)*7    (1 1 1 1 1 1 1 1 0 0)
(1)*8    (1 0 0 0 0 0 0 0 1 0)
 :

多項式の積で表せるので、「選んだスイッチの多重集合が同じなら、結果は操作順に依らない」こともわかる。

以下の点から考察を進める。

• 同じ値のスイッチのみをいっぱい選んだ時の挙動
• 違う値のスイッチを同時に選んだ時の挙動

$A_i=1$ がたくさんある場合を考える。
$A_i \gt 1$ の時も、同じ値のスイッチを繰り返し押すと横方向に $A_i$ だけ間延びしたパスカルの三角形となるので、 $N ← \left \lfloor \dfrac{N-1}{A_i} \right \rfloor +1$ と捉えれば、同じように考えられる。

$1$ のスイッチを $x$ 個選んだときの $B$ を、$f(x)$ とする。
$N$ が十分大きいならば、基本的には $f(x)$ が重複することはない。

ただし、$x$ が $N$ を超えてくると、右の方で切り捨てが発生する。そうなると $f(0)$ に戻り、ループしだす。

N=6     i 0 1 2 3 4 5
f(0)     (1 0 0 0 0 0)
f(1)     (1 1 0 0 0 0)
f(2)     (1 0 1 0 0 0)
f(3)     (1 1 1 1 0 0)
f(4)     (1 0 0 0 1 0)
f(5)     (1 1 0 0 1 1)
f(6)     (1 0 1 0 1 0)
f(7)     (1 1 1 1 1 1)
f(8)     (1 0 0 0 0 0)  ← f(0) に戻る
f(9)     (1 1 0 0 0 0)  ← これ以降は f(x-8) と同じになる
 :

$N$ を超えれば即座にループするわけではなく、 $x$ が「$N$ 以上で、$2^k$ と表せる値」になったら $f(0)$ に戻る。 それまでは $x$ 毎に異なった $f(x)$ となる。

したがって、$A$ に $1$ が $C_1$ 個ある場合、 それのみを選んだとすると $\min(C_1+1, 2^{\lceil \log_2{N} \rceil})$ 種類の $B$ ができる。

$A_i \gt 1$ の場合も、$N$ を変換すれば同じように求められる。

$A_i = y$ の場合のこの値を、$g(y)$ とする。

もし、$y$ 毎に独立、つまり 「可能な $B$ の種類数は $\displaystyle \prod_{y \in Set(A)}g(y)$」となる性質があったら楽だが。。。

実験すると、何となく成り立ちそうではあるものの、そう上手くはいかない。
サンプル3がそれを教えてくれる事例で、 $2^k$ 倍の関係にあるスイッチがあると、上手くいかなくなる。mod 2 の世界で以下が成り立つためである。

• $(1+x^a)^2 \equiv 1+x^{2a}$

よって、選んだスイッチの値の組について、$(1,1)$ と $(2,)$ の結果は等しい。
さらに、$(3,3),(6,)$ や、$(1,1,1,1),(1,1,2),(2,2),(4,)$ なども互いに等しくなる。

各 $A_i$ を $2^k \cdot d$（$d$ 奇数）として表現した時、$d$ が同じものは、 「$a$ が $2$ 個」と「$2a$ が $1$ 個」が等価なことで互いに干渉し合うとわかった。

では、他は？

• $d$ が異なるもの同士の組合せで、$B$ に与える影響が同じものはある？
• $d$ が同じもの同士で、個数が $2^k$ 倍の関係以外、例えば「$a$ が $3$ 個」と「$2^ka$ が $9$ 個」などで偶然、同じになるものはある？

それを確認するため、選んだスイッチの値の多重集合に対して 以下の手順をおこなえる限りおこなった結果を「標準形」とする。

• 同じ値 $a$ が $2$ 個含まれていたら、$2a$ の値 $1$ 個と入れ替える
• その結果、$2a \ge N$ となった要素は（操作上、$B$ に実質的な影響を及ぼさないので）除外する

標準化の過程や結果で初期のスイッチの値として存在しない値が含まれてもよいとする。 あくまで「同じ $B$ を作る集合が、同じ標準形に収束する」ことが重要なので。 この結果、標準形には同じ値は高々1回含まれている状態となる。

「標準形が異なる集合からは、異なる $B$ ができる」ことが言えれば、重複は $2^k$ の倍数の関係だけに限られることが言える。 言い換えると「ある標準形から構築された $B$ があれば、そこから標準形を一意に特定できる」ことを示せればよい。

これは以下の手順で構築可能である。

• $B$ で、$B_0$ の次に“1”が立っている場所を $x$ とする。
• $x$ を標準形に加える。
• $B$ を、$x$ を使わなかった場合の状態にする。（下の桁から、$x$ について操作する前の値を特定していける）
• $B_0$ 以外が “0” になるまで繰り返す。

ある標準形の最小値を $x$ とすると、最終的な $B$ において、$B_1～B_{x-1}$ は “0”、$B_x$ には必ず “1” が立っている。 $x+1$ 以上の操作によっては、$B_x$ 以下が変化することはないので。
逆に言うと、$B_1～B_{x-1}=0$、$B_x=1$ なら、$x$ は必ず標準形に入っていることになる。

よって、標準形が異なれば $B$ も異なることが言え、重複が発生するのは $2^k$ の倍数関係にある値が含まれる場合のみであることが分かる。

実際に、標準形を数える。
各 $A_i$ を $2^k \cdot d$（$d$ 奇数）として表現し、$d$ 毎に分類する。

例
Aの内訳  1*8, 2*3, 3*5, 4*1, 5*6, 6*2, 8*4
     ↓
         個数カウント
         k  0  1  2  3
    d=1     8  3  1  4
    d=3     5  2
    d=5     6

$d$ 毎に以下の問題を解けば、それが $d$ が同じ組の中で作れる $B$ の種類数となる。

• $k=0,1,...,n$ について、$2^k$ 円硬貨が $C_k$ 枚あります。
• これらで作れる $L$ 円未満の金額は何通りありますか？

$d$ が異なれば独立であることが言えたので、小問題の答えを $h(d)$ として、$\displaystyle \prod_{d}h(d)$ が全体の答えとなる。

小問題は下の桁からのDPで解ける。 $2^k$ 円硬貨を使って最終金額の $k$ bit 目に違いが出るのは使った枚数の偶奇だけで、 $0$ 枚使った場合、$1$ 枚使った場合、の2通りを試せば、残りは2枚セットで使うと考えてよくなる。 つまり、$2^{k+1}$ 円硬貨が $\left \lfloor \dfrac{C_k-\{0 or 1\}}{2} \right \rfloor$ 枚あるとして、桁を繰り上げて考えて差し支えない。

$L$ の値も迷うところで、$N$ を設定したくなるが、それだと上手くいかない。
先ほどの $f(x)$ の例では、$N=6$ を超えても、$f(7)$ まではできる $B$ に違いがあった。 ここでも同様に、$L=2^{\lceil \log_2{N} \rceil}$ を設定すればよい。 ただしここでの $N$ は、$\left \lfloor \dfrac{N-1}{d} \right \rfloor +1$ に置き換え済みの値とする。

++++ Python3

from collections import Counter, defaultdict


def count_below(bl, ccc):
    """ 2^i 円硬貨が ccc[i] 枚あるとき、作れる 2^bl 円未満の金額の種類数 """
    if len(ccc) <= bl:
        ccc += [0] * (bl + 1 - len(ccc))
    elif len(ccc) > bl + 1:
        ccc = ccc[:bl + 1]
    dp = {ccc[0]: 1}  # {k:v} : 着目中の 2^i 円硬貨が k 枚相当ある時の、金額の種類数
    for i in range(bl):
        c = ccc[i + 1]
        ndp = defaultdict(int)
        for k, v in dp.items():
            ndp[k // 2 + c] += v
            if k > 0:
                ndp[(k - 1) // 2 + c] += v
        dp = ndp
    return sum(dp.values())


def solve(n, m, aaa):
    MOD = 998244353
    cnt = Counter(aaa)
    cnt2 = defaultdict(list)
    for a, c in cnt.items():
        e = 0
        b = a
        while b & 1 == 0:
            e += 1
            b >>= 1
        if len(cnt2[b]) <= e:
            cnt2[b].extend([0] * (e - len(cnt2[b]) + 1))
        cnt2[b][e] += c

    ans = 1
    for b, ccc in cnt2.items():
        ans *= count_below(((n - 1) // b).bit_length(), ccc)
        ans %= MOD

    return ans


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