結果

問題 No.1821 LEQ-GEQ Permutations
コンテスト
ユーザー zkou
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 1 TLE * 12 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

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