AtCoder Beginner Contest 471 F,G問題メモ

from functools import cmp_to_key


def solve(n, k, sss):
    sort_by_len = [[] for _ in range(11)]
    for s in sss:
        sort_by_len[len(s)].append(s)
    sss2 = []
    for i in range(10, 0, -1):
        sort_by_len[i].sort(reverse=True)
        sss2.extend(sort_by_len[i])

    def cmp(a, b):
        ab = a + b
        ba = b + a
        if ab > ba:
            return -1
        elif ab < ba:
            return 1
        return 0

    key = cmp_to_key(cmp)

    top_k = sss2[:k]
    top_k.sort(key=key)
    ans = ''.join(top_k)
    ans = ans.lstrip('0')

    if n > k:
        mx = max(map(int, sss2[k:]))
        top_k1 = sss2[:k - 1]
        top_k1.sort(key=key)
        ans2 = str(mx) + ''.join(top_k1)
        ans2 = ans2.lstrip('0')

        if len(ans) < len(ans2):
            ans = ans2
        elif len(ans) == len(ans2) and ans < ans2:
            ans = ans2

    if ans == '':
        ans = '0'
    return ans


n, k = list(map(int, input().split()))
sss = [input() for _ in range(n)]
ans = solve(n, k, sss)
print(ans)

from collections import defaultdict


class NttConvolution:
    """
    NTT (Number Theoretic Transform) for Codon.
    MOD = 998244353 = 119 * 2^23 + 1, primitive root = 3.
    Maximum transform length: 2^23 = 8388608.

    Usage:
        ntt = NttConvolution()
        c = ntt.convolution(a, b)
        c = ntt.convolution_all([a, b, c, d])
        ntt.ntt(a)   # in-place forward transform
        ntt.intt(a)  # in-place inverse transform
    """

    _roots: list[int]
    _inv_roots: list[int]

    def __init__(self) -> None:
        _M = 998244353
        _G = 3
        _LOG2 = 23
        roots = [0] * (_LOG2 + 1)
        inv_roots = [0] * (_LOG2 + 1)
        roots[_LOG2] = NttConvolution._pow_mod(_G, (_M - 1) // (1 << _LOG2))
        inv_roots[_LOG2] = NttConvolution._pow_mod(roots[_LOG2], _M - 2)
        for i in range(_LOG2 - 1, -1, -1):
            roots[i] = roots[i + 1] * roots[i + 1] % _M
            inv_roots[i] = inv_roots[i + 1] * inv_roots[i + 1] % _M
        self._roots = roots
        self._inv_roots = inv_roots

    @staticmethod
    def _pow_mod(base: int, exp: int) -> int:
        _M = 998244353
        result = 1
        base %= _M
        while exp > 0:
            if exp & 1:
                result = result * base % _M
            exp >>= 1
            base = base * base % _M
        return result

    @staticmethod
    def _bit_length(n: int) -> int:
        k = 0
        while n > 0:
            k += 1
            n >>= 1
        return k

    def _transform(self, a: list[int], invert: bool) -> None:
        _M = 998244353
        n = len(a)
        k = NttConvolution._bit_length(n) - 1
        table = self._inv_roots if invert else self._roots

        j = 0
        for i in range(1, n):
            bit = n >> 1
            while j & bit:
                j ^= bit
                bit >>= 1
            j ^= bit
            if i < j:
                a[i], a[j] = a[j], a[i]

        length = 1
        for s in range(k):
            length <<= 1
            half = length >> 1
            w = table[s + 1]
            i = 0
            while i < n:
                wn = 1
                for t in range(half):
                    u = a[i + t]
                    v = a[i + t + half] * wn % _M
                    a[i + t] = (u + v) % _M
                    a[i + t + half] = (u - v + _M) % _M
                    wn = wn * w % _M
                i += length

        if invert:
            inv_n = NttConvolution._pow_mod(n, _M - 2)
            for i in range(n):
                a[i] = a[i] * inv_n % _M

    def ntt(self, a: list[int]) -> None:
        self._transform(a, False)

    def intt(self, a: list[int]) -> None:
        self._transform(a, True)

    def convolution(self, a: list[int], b: list[int]) -> list[int]:
        _M = 998244353
        n = len(a)
        m = len(b)
        if n == 0 or m == 0:
            return []
        result_len = n + m - 1

        if min(n, m) <= 60:
            c = [0] * result_len
            if n < m:
                for i in range(n):
                    ai = a[i]
                    if ai == 0:
                        continue
                    for j in range(m):
                        c[i + j] = (c[i + j] + ai * b[j]) % _M
            else:
                for j in range(m):
                    bj = b[j]
                    if bj == 0:
                        continue
                    for i in range(n):
                        c[i + j] = (c[i + j] + a[i] * bj) % _M
            return c

        sz = 1
        while sz < result_len:
            sz <<= 1

        fa = [0] * sz
        fb = [0] * sz
        for i in range(n):
            fa[i] = a[i] % _M
        for i in range(m):
            fb[i] = b[i] % _M

        self._transform(fa, False)
        self._transform(fb, False)

        for i in range(sz):
            fa[i] = fa[i] * fb[i] % _M

        self._transform(fa, True)
        return fa[:result_len]

    def convolution_all(self, polys: list[list[int]]) -> list[int]:
        from collections import deque
        if len(polys) == 0:
            return [1]
        q: deque[list[int]] = deque(polys)
        while len(q) > 1:
            a = q.popleft()
            b = q.popleft()
            q.append(self.convolution(a, b))
        return q[0]


def solve(n, k, seed, m, bbb, vvv):
    def make_input():
        aaa = bbb
        state = seed
        mask46 = (1 << 46) - 1
        mask5 = (1 << 5) - 1
        mask32 = (1 << 32) - 1
        mask64 = (mask32 << 32) | mask32
        for i in range(m, n):
            x = ((((state >> 18) & mask46) ^ state) >> 27) & mask32
            r = (state >> 59) & mask5
            y = ((x >> r) + (x << (32 - r))) & mask32
            aaa.append(y % k)
            state = (state * 6364136223846793005 + 2026081520260815) & mask64
            if state < 0:
                state += mask64 + 1
            # print(f'{i=} {x=} {r=} {y=}')
        return aaa

    aaa = make_input()
    cnt1 = defaultdict(int)
    # defaultdict(lambda: defaultdict(int)) はCodonコンパイラがセグフォするため不可
    cnt2 = {}
    for i in range(n):
        a1 = aaa[i]
        cnt1[a1] += 1
        if i < n - 1:
            a2 = aaa[i + 1]
            if a1 > a2:
                a1, a2 = a2, a1
            d = a2 - a1
            if d <= k - d:
                d, a = d, a1
            else:
                d, a = k - d, a2
            if d not in cnt2:
                cnt2[d] = defaultdict(int)
            cnt2[d][a] += 1

    # print(cnt1)
    # print(cnt2)

    def naive(d, subcnt, ans):
        for a, c in subcnt.items():
            for i in range(k):
                j1 = (a + i) % k
                j2 = (a + i + d) % k
                if vvv[j1] == 1 and vvv[j2] == 1:
                    ans[i] -= c

    def convolve(d, subcnt, conv, ans):
        www = [0] * (k * 2)
        for j1 in range(k):
            j2 = (j1 + d) % k
            if vvv[j1] == 1 and vvv[j2] == 1:
                www[j1] += 1
                www[j1 + k] += 1
        xxx = [0] * k
        for a, c in subcnt.items():
            xxx[k - a - 1] += c
        yyy = conv.convolution(www, xxx)
        for i in range(k):
            ans[i] -= yyy[i + k - 1]

    ans = [0] * k
    conv = NttConvolution()
    for a, c in cnt1.items():
        for i in range(k):
            j = (a + i) % k
            if vvv[j] == 1:
                ans[i] += c
    for d, subcnt in cnt2.items():
        # dummy1 = [0] * k
        # dummy2 = [0] * k
        # naive(d, subcnt, dummy1)
        # convolve(d, subcnt, conv, dummy2)
        # print(f'{dummy1=}')
        # print(f'{dummy2=}')
        if len(subcnt) < 200:
            naive(d, subcnt, ans)
        else:
            convolve(d, subcnt, conv, ans)

    return ans


n, k, seed, m = list(map(int, input().split()))
bbb = list(map(int, input().split()))
vvv = list(map(int, input().split()))
ans = solve(n, k, seed, m, bbb, vvv)
print('\n'.join(map(str, ans)))