AtCoder Regular Contest 191 (Div. 2) A,B,C,D,E問題メモ

def naive(n, m, s, t):
    from itertools import product
    s = list(map(int, s))
    t = list(map(int, t))
    ans = ''
    for p in product(range(n), repeat=m):
        tmp = s.copy()
        for j, i in enumerate(p):
            tmp[i] = t[j]
        ans = max(ans, ''.join(map(str, tmp)))
    return ans


def solve(n, m, s, t):
    ans = list(map(int, s))
    t = list(map(int, t))
    st = sorted(t, reverse=True)

    i = 0
    for c in st:
        while i < n and ans[i] >= c:
            i += 1
        if i >= n:
            break
        ans[i] = c
        i += 1

    if min(ans) > t[-1]:
        ans[-1] = t[-1]

    ans = ''.join(map(str, ans))
    return ans


n, m = map(int, input().split())
s = input()
t = input()
ans = solve(n, m, s, t)
print(ans)


def test():
    import random
    n = 6
    m = 6
    for _ in range(100):
        s = random.choices(range(1, 10), k=n)
        t = random.choices(range(1, 10), k=m)
        s = ''.join(map(str, s))
        t = ''.join(map(str, t))
        ans1 = solve(n, m, s, t)
        ans2 = naive(n, m, s, t)
        if ans1 == ans2:
            continue
        print(s, t, ans1, ans2)

# test()

def solve(n, k):
    bn = f'{n:b}'
    zc = bn.count('0')
    if 2 ** zc < k:
        return -1
    k -= 1
    zero_pos = []
    res = list(map(int, bn[::-1]))
    for i, c in enumerate(res):
        if c == 0:
            zero_pos.append(i)
    i = 0
    while k:
        if k & 1:
            res[zero_pos[i]] = 1
        k >>= 1
        i += 1
    res.reverse()
    ans = int(''.join(map(str, res)), base=2)
    return ans


t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    print(solve(n, k))

from collections import defaultdict


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 factors


def suspect(a, t, n):
    x = pow(a, t, n)
    n1 = n - 1
    while t != n1 and x != 1 and x != n1:
        x = pow(x, 2, n)
        t <<= 1
    return t & 1 or x == n1


def miller_rabin(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    check_list = (2, 7, 61) if n < (1 << 32) else (2, 325, 9375, 28178, 450775, 9780504, 1795265022)
    for i in check_list:
        if i >= n:
            break
        if not suspect(i, d, n):
            return False
    return True


def solve(t, cases):
    primes = get_primes(10 ** 5)
    ans = []
    for n in cases:
        if n == 1:
            ans.append('1 1')
            continue
        p = -1
        for k in range(2, 100000, 2):
            cp = k * n + 1
            if miller_rabin(cp):
                p = cp
                break
        assert p != -1

        pfn = prime_factorize(n, primes)
        for a in range(2, p):
            if pow(a, n, p) != 1:
                continue
            ok = True
            for q in pfn.keys():
                if pow(a, n // q, p) == 1:
                    ok = False
                    break
            if ok:
                ans.append(f'{a} {p}')
                break

    return ans


t = int(input())
cases = [int(input()) for _ in range(t)]
ans = solve(t, cases)
print('\n'.join(ans))

from collections import deque


def bfs(s, t, links, return_path):
    """ s から「t を通り越さずに」行ける各頂点への最短距離 """
    q = deque([s])
    dists = [1 << 60] * n
    dists[s] = 0
    predecessors = [-1] * n
    while q:
        u = q.popleft()
        du = dists[u]
        dv = du + 1
        for v in links[u]:
            if dists[v] > dv:
                dists[v] = dv
                predecessors[v] = u
                if v != t:
                    q.append(v)
    if not return_path:
        return dists

    path = []
    v = t
    while v != -1:
        path.append(v)
        v = predecessors[v]
    path.reverse()
    return dists, path


def solve(n, m, s, t, edges):
    s -= 1
    t -= 1
    links = [[] for _ in range(n)]
    degrees = [0] * n
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].append(v)
        links[v].append(u)
        degrees[u] += 1
        degrees[v] += 1

    # パスグラフはすれ違えない。
    if all(d <= 2 for d in degrees) and any(d == 1 for d in degrees):
        return -1

    INF = 1 << 60
    dists_s, shortest_path = bfs(s, t, links, True)
    dists_t = bfs(t, s, links, False)

    first_best = dists_s[t]

    second_best = INF
    ssp = set(shortest_path)
    for i in range(n):
        if i in ssp:
            continue
        second_best = min(second_best, dists_s[i] + dists_t[i])
    ans1 = first_best + second_best

    # S-T 間はパスグラフで、最寄りの三叉路までともに行ってすれ違わないといけないケース
    # second_best がとても長い場合、こちらの方が近いこともある。
    nearest_junction = INF
    for i in range(n):
        if degrees[i] >= 3:
            nearest_junction = min(nearest_junction, dists_s[i], dists_t[i])
    ans2 = first_best * 2 + (nearest_junction + 1) * 4

    return min(ans1, ans2)


n, m, s, t = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, s, t, edges)
print(ans)

from pprint import pprint

import numpy as np


def naive1():
    # 1つの山だけのゲーム
    x = 2
    y = 2

    # memo[a,b,t] := t=0先手/1後手 に、金貨a枚、銀貨b枚で回ってきたときに、0:先手必勝/1:必敗
    memo = {}

    def check(a, b, t):
        if a == 0 and b == 0:
            return t ^ 1
        if (a, b, t) in memo:
            return memo[a, b, t]
        win = t ^ 1
        if b > 0 and check(a, b - 1, t ^ 1) == t:
            win = t
        z = x if t == 0 else y
        if a > 0 and check(a - 1, b + z, t ^ 1) == t:
            win = t
        memo[a, b, t] = win
        return win

    sa = 10
    sb = 10
    print(check(sa, sb, 0))
    print(check(sa, sb, 1))

    mb = max(b for a, b, t in memo)
    res0 = [[8] * (mb + 1) for _ in range(sa + 1)]
    res1 = [[8] * (mb + 1) for _ in range(sb + 1)]
    res0[0][0] = 1
    res1[0][0] = 0
    for (a, b, t), r in memo.items():
        if t == 0:
            res0[a][b] = r
        else:
            res1[a][b] = r

    pprint(res0, width=200)
    pprint(res1, width=200)


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 _convolve(f, g):
    # 小さいうちは愚直の方が高速。convolve_mod()と併用するなら大丈夫だが、単独で使用する場合はオーバーフローに注意
    if len(f) * len(g) < 10000:
        return np.convolve(f, g)

    fft_len = 1
    true_len = len(f) + len(g) - 1
    while fft_len < true_len:
        fft_len <<= 1

    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    Fh = Ff * Fg

    h = np.fft.irfft(Fh, fft_len)
    h = np.rint(h).astype(np.int64)

    return h[:true_len]


def convolve_mod(f, g, p):
    f1, f2 = np.divmod(f, 1 << 15)
    g1, g2 = np.divmod(g, 1 << 15)

    a = _convolve(f1, g1) % p
    c = _convolve(f2, g2) % p
    b = (_convolve(f1 + f2, g1 + g2) - (a + c)) % p

    h = (a << 30) + (b << 15) + c
    return h % p


def solve(n, x, y, coins):
    if x % 2 == 0:
        if y % 2 == 0:
            judge0 = lambda a, b: (a ^ b ^ 1) & 1
            judge1 = lambda a, b: (a ^ b) & 1
        else:
            judge0 = lambda a, b: 0 if a > 0 else (b + 1) % 2
            judge1 = lambda a, b: 0 if a > 1 else b % 2
    else:
        if y % 2 == 0:
            judge0 = lambda a, b: 1 if a > 1 else (b + 1) % 2
            judge1 = lambda a, b: 1 if a > 0 else b % 2
        else:
            judge0 = lambda a, b: (b + 1) % 2
            judge1 = lambda a, b: b % 2

    win = [[0, 0], [0, 0]]
    for a, b in coins:
        win[judge0(a, b)][judge1(a, b)] += 1

    p, q = win[0]
    r, s = win[1]
    c1 = [0] * (p + 1)
    c2 = [0] * (q * 2 + 1)
    c3 = [0] * (s + 1)
    MOD = 998244353
    facts, finvs = precompute_factorials(max(p, q, s), MOD)

    for i in range(p + 1):
        c1[i] = facts[p] * finvs[i] * finvs[p - i] % MOD
    for j in range(q + 1):
        c2[j * 2] = facts[q] * finvs[j] * finvs[q - j] % MOD
    for l in range(s + 1):
        c3[l] = facts[s] * finvs[l] * finvs[s - l] % MOD

    c12 = convolve_mod(c1, c2, MOD)
    c123 = convolve_mod(c12, c3, MOD)
    ans = sum(c123[q + s + 1:]) % MOD
    ans *= pow(2, r, MOD)
    ans %= MOD
    return ans


n, x, y = map(int, input().split())
coins = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, x, y, coins)
print(ans)