結果

問題 No.1821 LEQ-GEQ Permutations
ユーザー zkouzkou
提出日時 2022-01-21 22:21:02
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,716 bytes
コンパイル時間 282 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 1,349,684 KB
最終ジャッジ日時 2024-11-26 00:51:48
合計ジャッジ時間 57,100 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
65,024 KB
testcase_01 AC 50 ms
372,556 KB
testcase_02 AC 49 ms
65,408 KB
testcase_03 MLE -
testcase_04 AC 48 ms
66,724 KB
testcase_05 AC 48 ms
64,896 KB
testcase_06 WA -
testcase_07 MLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 AC 869 ms
105,508 KB
testcase_11 MLE -
testcase_12 TLE -
testcase_13 MLE -
testcase_14 TLE -
testcase_15 MLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

table_len = 10 ** 4 + 10

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)

finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, 0, -1):
    finv[i-1] = finv[i] * i % MOD

def comb(n, k):
    if k < 0 or n < 0 or n - k < 0:
        return 0
    return fac[n] * finv[k] % MOD * finv[n - k] % MOD

def perm(n, k):
    if k < 0 or n < 0 or n - k < 0:
        return 0
    return fac[n] * finv[n - k] % MOD

N = int(input())
S = input()

U = S.count('0')
D = S.count('1')

dp = [[0] * (N) for _ in range(N)]
dp[0][0] = 1
answer = fac[N]
for i in range(N):
    new_dp = [[0] * (N) for _ in range(N)]
    for s in range(N):
        for u in range(N):
            if dp[u][s] == 0:
                continue
            nu = u
            ns = s + 1
            if ns < N:
                new_dp[nu][ns] += dp[u][s]
                new_dp[nu][ns] %= MOD
                if ns - 1 >= 0:
                    new_dp[nu][ns - 1] += dp[u][s] * (ns - 1)
                    new_dp[nu][ns - 1] %= MOD
                    if nu + 1 < N:
                        new_dp[nu + 1][ns - 1] += dp[u][s] * (ns - 1)
                        new_dp[nu + 1][ns - 1] %= MOD
                        if ns - 2 >= 0:
                            new_dp[nu + 1][ns - 2] += dp[u][s] * (ns - 1) * (ns - 1)
                            new_dp[nu + 1][ns - 2] %= MOD
    dp = new_dp
    for u in range(1, N):
        d = i + 1 - u
        if not 0 < d < N or u > U or d > D:
            continue
        e = N - u - d
        # print(u, d, e, dp[u][0])
        answer += dp[u][0] * perm(N, e) % MOD * perm(U, u) % MOD * perm(D, d) % MOD
        answer %= MOD


print(answer)
0