第七回日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 464）F,G問題メモ

# noinspection PyUnresolvedReferences
# noinspection PyTypeChecker
@extend
class int:
    def bit_length(self) -> int:
        return 64 - abs(self).__ctlz__()

    def bit_count(self) -> int:
        return abs(self).__ctpop__()


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 solve(n, x, aaa):
    MOD = 998244353

    if n == 1:
        return aaa[0] % MOD

    def get_partial_sum(aaa):
        n = len(aaa)
        total = [0] * (1 << n)
        for bitset in range(1, 1 << n):
            lsb = bitset & -bitset
            i = lsb.bit_length() - 1
            val = total[bitset ^ lsb] + aaa[i]
            total[bitset] = val
        return total

    facts, finvs = precompute_factorials(n, MOD)

    # 採用する集合 S を固定し、最後に Ak を採用して x 以上になるという組 (S,k) 1つにつき、そうなる確率（ i=|S| のみに依存）
    ppp = [0] * n
    for i in range(n):
        ppp[i] = facts[i] * facts[n - 1 - i] % MOD * finvs[n] % MOD

    n1 = n // 2
    n2 = n - n1

    nm = max(n1, n2)
    bit_counts = [0] * (1 << nm)
    for bitset in range(1, 1 << nm):
        lsb = bitset & -bitset
        bit_counts[bitset] = bit_counts[bitset ^ lsb] + 1

    bbb = aaa[:n1]
    ccc = aaa[n1:]
    lll = get_partial_sum(bbb)
    rrr = get_partial_sum(ccc)

    def get_expected(n1, n2, bbb, lll, rrr):
        rrr_by_size = [[] for _ in range(n2 + 1)]
        acc_by_size = []
        for bitset in range(1 << n2):
            rrr_by_size[bit_counts[bitset]].append(rrr[bitset])
        for size in range(n2 + 1):
            rbs = rrr_by_size[size]
            rbs.sort()
            acc = [0] * (len(rbs) + 1)
            for i in range(len(rbs)):
                acc[i + 1] = (acc[i] + rbs[i]) % MOD
            acc_by_size.append(acc)

        l_sums_full = [(lll[bitset], bitset, bit_counts[bitset]) for bitset in range(1 << n1)]
        l_sums_full.sort(reverse=True)

        result = 0
        for i in range(n1):
            a = bbb[i]
            bit = 1 << i
            l_sums = [item for item in l_sums_full if item[1] & bit == 0]
            for s2 in range(n2 + 1):
                rbs = rrr_by_size[s2]
                cbs = acc_by_size[s2]
                m = len(rbs)
                l = 0
                r = 0
                for wl, _, s1 in l_sums:
                    lo_lim = x - a - wl
                    hi_lim = x - wl
                    while r < m and rbs[r] < hi_lim:
                        r += 1
                    while l < m and rbs[l] < lo_lim:
                        l += 1
                    cnt = r - l
                    if cnt > 0:
                        tmp = (cbs[r] - cbs[l]) % MOD
                        tmp = (tmp + (a + wl) % MOD * cnt) % MOD
                        result += tmp * ppp[s1 + s2]
                        result %= MOD
        return result

    ans_l = get_expected(n1, n2, bbb, lll, rrr)
    ans_r = get_expected(n2, n1, ccc, rrr, lll)
    ans = (ans_l + ans_r) % MOD
    if ans < 0:
        ans += MOD
    return ans


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

from heapq import heapify, heappush, heappop


def solve(n, s):
    INF = 1 << 60
    diff = [INF] * (n + 1)
    left = list(range(-1, n + 1))
    right = list(range(1, n + 3))
    available = [True] * (n + 1)
    hq = []
    for i in range(1, n):
        diff[i] = int(s[i - 1] != 'R') + int(s[i] != 'S')
        hq.append((diff[i], i))
    heapify(hq)

    costs = [0] * (n + 1)
    cur = 0
    for k in range(1, n // 2 + 1):
        while available[hq[0][1]] == False:
            heappop(hq)
        cost, i = heappop(hq)
        cur += cost
        costs[cur] = k
        l = left[i]
        r = right[i]
        ll = left[l]
        rr = right[r]
        available[l] = False
        available[r] = False
        left[i] = ll
        right[i] = rr
        left[rr] = i
        right[ll] = i
        diff[i] = diff[l] + diff[r] - cost
        heappush(hq, (diff[i], i))

    for i in range(1, n + 1):
        costs[i] = max(costs[i], costs[i - 1])
    return costs


t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ans = solve(n, s)
    print(' '.join(map(str, ans)))