ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）E,F,G 問題メモ

def precalc():
    def get_spf(n):
        """ nまでの各数を割り切る一番小さな素数 """
        spf = list(range(n + 1))
        for i in range(2, n + 1, 2):
            spf[i] = 2
        for p in range(3, int(n ** 0.5) + 1, 2):
            if spf[p] == p:
                for m in range(p * p, n + 1, 2 * p):
                    if spf[m] == m:
                        spf[m] = p
        return spf

    def prime_factorize(x, spf):
        """ xを素因数分解、{素数: 個数} の辞書で返す """
        factors = {}
        prev = -1
        cnt = 0
        while x > 1:
            if spf[x] == prev:
                cnt += 1
            else:
                if prev != -1:
                    factors[prev] = cnt
                prev = spf[x]
                cnt = 1
            x //= spf[x]
        if prev != -1:
            factors[prev] = cnt
        return factors

    spf = get_spf(5000)
    result = [{}, {}]
    for i in range(2, 5001):
        pf = prime_factorize(i, spf)
        tmp = result[-1].copy()
        for p, c in pf.items():
            if p in tmp:
                tmp[p] += c
            else:
                tmp[p] = c
        result.append(tmp)
    return result


def solve(n, m, ccc, pf):
    t = sum(ccc)
    total = pf[t].copy()
    for c in ccc:
        tmp = pf[c]
        for p, cnt in tmp.items():
            total[p] -= cnt
    ans = 1
    for p, cnt in total.items():
        ans *= pow(p, cnt, m)
        ans %= m
    return ans


t, m = map(int, input().split())
pf = precalc()
for _ in range(t):
    n = int(input())
    ccc = list(map(int, input().split()))
    ans = solve(n, m, ccc, pf)
    print(ans)

def solve(n, t):
    def iter_bit(x):
        i = 0
        while x:
            if x & 1:
                yield i
            x >>= 1
            i += 1

    t = [ord(c) - 97 for c in t]
    MOD = 998244353
    n2 = 1 << n
    dp = [0] * n2
    dp[-1] = 1
    for bitset in range(n2 - 1, 0, -1):
        prev = -1
        for i in iter_bit(bitset):
            if t[i] == prev:
                continue
            prev = t[i]
            new_key = bitset ^ (1 << i)
            dp[new_key] += dp[bitset]
            dp[new_key] %= MOD
    return dp[0]


n = int(input())
t = input()
ans = solve(n, t)
print(ans)

def solve(n, m, aaa):
    def sub(r, aaa, bit, depth=0):
        """ 0 <= x < r の値を aaa と xor した時の最小値の総和, ただし max(aaa) の 最上位bit は bit 以下であることが保証 """

        # r が 2 のべき乗で、ちょうど真ん中が bit である構造かどうか（bit は常に 2 のべき乗）
        is_powered_r = r == (bit << 1)

        if is_powered_r and len(aaa) == 1:
            return r * (r - 1) // 2

        # 十分小さければ愚直計算
        if r * len(aaa) < 500:
            ans = 0
            for i in range(r):
                ans += min(a ^ i for a in aaa)
            return ans

        aaa0 = []
        aaa1 = []
        for a in aaa:
            if a & bit:
                aaa1.append(a ^ bit)
            else:
                aaa0.append(a)

        if len(aaa0) == 0:
            if r <= bit:
                ans = sub(r, aaa1, bit >> 1, depth + 1) + bit * r
            elif is_powered_r:
                ans = sub(bit, aaa1, bit >> 1, depth + 1) * 2 + bit * bit
            else:
                ans = sub(bit, aaa1, bit >> 1, depth + 1) + sub(r - bit, aaa1, bit >> 1, depth + 1) + bit * bit
            return ans
        elif len(aaa1) == 0:
            if r <= bit:
                ans = sub(r, aaa0, bit >> 1, depth + 1)
            elif is_powered_r:
                ans = sub(bit, aaa0, bit >> 1, depth + 1) * 2 + bit * bit
            else:
                ans = sub(bit, aaa0, bit >> 1, depth + 1) + sub(r - bit, aaa0, bit >> 1, depth + 1) + (r - bit) * bit
            return ans

        if r <= bit:
            ans = sub(r, aaa0, bit >> 1, depth + 1)
        else:
            ans = sub(bit, aaa0, bit >> 1, depth + 1) + sub(r - bit, aaa1, bit >> 1, depth + 1)
        return ans

    aaa = list(set(aaa))
    ans = sub(m, aaa, 1 << 30)
    return ans


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