結果

問題 No.1821 LEQ-GEQ Permutations
ユーザー zkouzkou
提出日時 2022-01-21 22:21:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,716 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 87,120 KB
実行使用メモリ 317,116 KB
最終ジャッジ日時 2023-08-17 06:31:54
合計ジャッジ時間 8,047 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
80,964 KB
testcase_01 AC 76 ms
76,276 KB
testcase_02 AC 79 ms
76,352 KB
testcase_03 AC 76 ms
76,268 KB
testcase_04 AC 77 ms
76,308 KB
testcase_05 AC 78 ms
76,376 KB
testcase_06 WA -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

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