solution

多項式として整理しイデアルを使う。桁DP。計算量は \(d = \max(\log X, \log A_1, \log A_2, \dots, \log A_N)\) とおいて $O(Nd^2)$。

各整数は多項式 \(X, A_1, A_2, \dots, A_N \in \mathbb{F} _ 2[x]\) として見れる。 $2$倍する操作は \(f \in \mathbb{F} _ 2[x]\) から \(xf\) を作るような操作であり、xorの操作はそのまま加法である。 よって問題はideal \(I = (A_1, A_2, \dots, A_N)\) を考え \(\mathrm{ans} = \# \left\{ f \in I \mid f \le X \right\}\) を求めるものと言い換えられる。 ただしここで比較 \(\le\) は整数として見てのもの。 体上の$1$変数多項式環はEuclid環であることを思い出せば、これはもちろん単項イデアル整域でもあるので \(I = (g)\) であるような \(g \in \mathbb{F} _ 2[x]\) が \(g = \mathrm{gcd}(A_1, A_2, \dots, A_N)\) として一意に存在する。 よって求めるものは \(\mathrm{ans} = \# \left\{ a \in \mathbb{F} _ 2[x] \mid a g \le X \right\}\) 。 これは $a$ の高次の係数から決めていく桁DPをすれば求まる。

note

行列として整理しようとして破綻した。 editorialを覗いて「多項式」という単語が目に入ったとたんに解けた。 競プロの問題を代数学で殴るの楽しい。

implementation

#!/usr/bin/env python3
def divmod(f, g):
    assert g
    h = 0
    for i in reversed(range(f.bit_length() - g.bit_length() + 1)):
        if f & (1 << (g.bit_length() + i - 1)):
            f ^= g << i
            h ^= 1 << i
    return h, f

def gcd(f, g):
    while g:
        q, r = divmod(f, g)
        f, g = g, r
    return f

import functools
def solve(n, x, a):
    # (g) = (a_1, ..., a_n) is a principal ideal since F_2[x] is a PID
    g = functools.reduce(gcd, a)

    # count h in F_2[x] s.t. h g <= x
    cnt = 0
    h = 0
    for k in reversed(range(x.bit_length() - g.bit_length() + 1)):
        bit = 1 << (g.bit_length() + k - 1)
        if (x & bit):
            cnt += 1 << k
        if (x & bit) != (h & bit):
            h ^= g << k
    cnt += (h <= x)
    return cnt % 998244353


def main():
    n, x = input().split()
    n = int(n)
    x = int(x, 2)
    a = [ int(input(), 2) for _ in range(n) ]
    print(solve(n, x, a))

if __name__ == '__main__':
    main()