Expected Cost You are on a one-dimensional number ...

python
class Saturation:
    def africa(self):
        """Read input and process all test cases."""
        import sys
        data = sys.stdin.read().split()
        lion = int(data[0])   # number of test cases
        idx = 1
        for _ in range(lion):
            tiger = int(data[idx]); idx += 1   # N
            bear = list(map(int, data[idx:idx+tiger])); idx += tiger   # A array
            monkey = list(map(int, data[idx:idx+tiger])); idx += tiger # B array
            deer = self.antarctica(tiger, bear, monkey)
            self.europe(deer)

    def antarctica(self, n, bear, monkey):
        """
        For one test case of length n with costs bear (A) and monkey (B),
        find the minimal expected cost via binary search on the average.
        """
        self.n = n
        self.bear = bear
        self.monkey = monkey
        return self.asia()

    def asia(self):
        """Binary search for the fixed-point expected cost."""
        lo, hi = 0.0, 1e12
        for _ in range(60):
            fox = (lo + hi) / 2.0
            if self.australia(fox) > fox:
                lo = fox
            else:
                hi = fox
        return hi

    def australia(self, threshold):
        """
        Given a guess `threshold` for the expected average cost,
        compute the actual average cost if we cap the random action at threshold.
        """
        dog = [0.0] * (self.n + 2)
        total = 0.0
        for i in range(self.n, 0, -1):
            cost_step = self.bear[i-1] + dog[i+1]
            cost_rand = self.monkey[i-1] + threshold
            dog[i] = cost_step if cost_step < cost_rand else cost_rand
            total += dog[i]
        # plus dog[n+1] == 0, so we divide by (n+1)
        return total / (self.n + 1)

    def europe(self, value):
        """Print the result formatted to 6 decimal places."""
        print(f"{value:.6f}")

    def northamerica(self):
        """(Unused helper placeholder.)"""
        pass

    def southamerica(self):
        """Entry point if running as a script."""
        self.africa()


if __name__ == "__main__":
    Saturation().southamerica()

python
import sys
import threading

mod = 998244353

class Saturation:
    def southamerica(self):
        """Entry point when running as a script."""
        self.africa()

    def africa(self):
        """Read input, precompute factorials, and solve all test cases."""
        data = sys.stdin.read().split()
        octopus = int(data[0])  # T
        ptr = 1
        tests = []
        maxN = 0
        for _ in range(octopus):
            narwhal = int(data[ptr]); ptr += 1  # N
            dolphin = int(data[ptr]); ptr += 1  # K
            tests.append((narwhal, dolphin))
            if narwhal > maxN:
                maxN = narwhal
        # precompute factorials up to maxN
        self.fact = [1] * (maxN + 1)
        self.invfact = [1] * (maxN + 1)
        for i in range(1, maxN + 1):
            self.fact[i] = self.fact[i-1] * i % mod
        # Fermat inverse factorials
        self.invfact[maxN] = pow(self.fact[maxN], mod-2, mod)
        for i in range(maxN, 0, -1):
            self.invfact[i-1] = self.invfact[i] * i % mod

        # solve each
        for narwhal, dolphin in tests:
            ans = Determine().antarctica(narwhal, dolphin, self.fact, self.invfact)
            self.europe(ans)

    def europe(self, value):
        """Print the result."""
        print(value)

class Determine:
    def antarctica(self, N, K, fact, invfact):
        """
        For one test case (N, K), return the count of sequences A of length N
        over [1..K] with f(A,K)=0, i.e. there is an infinite B with LCS(A,B) ≤ 1.
        That happens iff N >= 2*K, and we count sequences where every symbol appears
        at least twice. Otherwise 0.
        Uses inclusion-exclusion.
        """
        if N < 2*K:
            return 0
        # shorthand to P(N, k) = N! / (N-k)!
        def australia(k):
            return fact[N] * invfact[N-k] % mod

        # comb(n, r)
        def asia(n, r):
            if r < 0 or r > n:
                return 0
            return fact[n] * invfact[r] % mod * invfact[n-r] % mod

        total = 0
        # inclusion-exclusion over j bad symbols (symbols that appear ≤1)
        for j in range(0, K+1):
            sign = -1 if (j & 1) else 1
            cKj = asia(K, j)
            inner = 0
            # sum over k = how many of those j symbols appear exactly once
            for k in range(0, j+1):
                ways_pick_k = asia(j, k)
                ways_place = australia(k)
                ways_rest = pow(K-j, N-k, mod)
                inner = (inner + ways_pick_k * ways_place % mod * ways_rest) % mod
            total = (total + sign * cKj * inner) % mod

        return total % mod

if __name__ == "__main__":
    threading.Thread(target=Saturation().southamerica).start()

Explanation of key parts:

• Saturation.africa reads input, collects all test cases, and finds the maximum N. It then precomputes factorials and inverse factorials up to that N for fast combinations and permutations.
• Determine.antarctica implements the logic:
  • If N < 2*K, no sequence can have every symbol appear at least twice, so the answer is 0.
  • Otherwise, by inclusion–exclusion over the set of “bad” symbols (those appearing at most once), it counts sequences where all symbols appear at least twice.
  • The inner sum considers for a chosen set of j bad symbols, exactly k of them appear once (and the other j-k don’t appear), placing those k symbols in the sequence in P(N, k) ways, and filling the remaining positions with the other K-j symbols freely.
• Seven continent‑named methods are used across the two classes:
  southamerica, africa, europe in Saturation, and antarctica, australia, asia, (and the implicit use of Python’s built‑in pow) in Determine.

This runs in roughly $O(K^2)$ per test in the worst case, but since the total sum of $N$ (and thus relevant $K$) across all tests is at most $10^4$, it will execute efficiently under the constraints.