Submission #55080816

Source Code Expand

MOD = 998244353

def mod_inv(x):
    return pow(x, MOD - 2, MOD)

def solve(N, K):
    dp = [[0] * (N + 1) for _ in range(K + 1)]
    dp[0][1] = 1

    inv_N2 = mod_inv(N * N)
    p_stay = (N * N - 2 * (N - 1)) * inv_N2 % MOD
    p_move = 2 * inv_N2 % MOD

    for i in range(1, K + 1):
        for j in range(1, N + 1):
            dp[i][j] = dp[i-1][j] * p_stay % MOD
            for k in range(1, N + 1):
                if k != j:
                    dp[i][j] = (dp[i][j] + dp[i-1][k] * p_move) % MOD

    expected_value = 0
    for j in range(1, N + 1):
        expected_value = (expected_value + j * dp[K][j]) % MOD

    return expected_value

N, K = map(int, input().split())
result = solve(N, K)
print(result)

Submission Info

Submission Time
Task E - Random Swaps of Balls
User mu16
Language Python (PyPy 3.10-v7.3.12)
Score 0
Code Size 745 Byte
Status RE
Exec Time 2214 ms
Memory 3629868 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 450
Status
AC × 3
AC × 9
TLE × 1
RE × 21
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_internal_00.txt, 01_internal_01.txt, 01_internal_02.txt, 01_internal_03.txt, 01_internal_04.txt, 01_internal_05.txt, 01_internal_06.txt, 01_internal_07.txt, 01_internal_08.txt, 01_internal_09.txt, 01_internal_10.txt, 01_internal_11.txt, 01_internal_12.txt, 01_internal_13.txt, 01_internal_14.txt, 01_internal_15.txt, 01_internal_16.txt, 01_internal_17.txt, 01_internal_18.txt, 01_internal_19.txt, 01_internal_20.txt, 01_internal_21.txt, 01_internal_22.txt, 01_internal_23.txt, 01_internal_24.txt, 01_internal_25.txt, 01_internal_26.txt, 01_internal_27.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 55 ms 76884 KiB
00_sample_01.txt AC 55 ms 76744 KiB
00_sample_02.txt AC 54 ms 76468 KiB
01_internal_00.txt AC 55 ms 76564 KiB
01_internal_01.txt AC 62 ms 82324 KiB
01_internal_02.txt AC 426 ms 94584 KiB
01_internal_03.txt TLE 2214 ms 151804 KiB
01_internal_04.txt AC 148 ms 84872 KiB
01_internal_05.txt AC 121 ms 96864 KiB
01_internal_06.txt AC 1602 ms 112700 KiB
01_internal_07.txt RE 1604 ms 3629028 KiB
01_internal_08.txt RE 1864 ms 3628444 KiB
01_internal_09.txt RE 1591 ms 3629256 KiB
01_internal_10.txt RE 1601 ms 3629284 KiB
01_internal_11.txt RE 1746 ms 3628556 KiB
01_internal_12.txt RE 1571 ms 3628096 KiB
01_internal_13.txt RE 1723 ms 3628852 KiB
01_internal_14.txt RE 1641 ms 3628304 KiB
01_internal_15.txt RE 1677 ms 3629088 KiB
01_internal_16.txt RE 1700 ms 3628084 KiB
01_internal_17.txt RE 419 ms 104256 KiB
01_internal_18.txt RE 1385 ms 3629868 KiB
01_internal_19.txt RE 1857 ms 3628956 KiB
01_internal_20.txt RE 1654 ms 3629264 KiB
01_internal_21.txt RE 1665 ms 3629760 KiB
01_internal_22.txt RE 415 ms 103948 KiB
01_internal_23.txt RE 1398 ms 3629096 KiB
01_internal_24.txt RE 1660 ms 3629524 KiB
01_internal_25.txt RE 1662 ms 3628856 KiB
01_internal_26.txt RE 1773 ms 3629408 KiB
01_internal_27.txt RE 459 ms 103976 KiB