結果

問題 No.2068 Restricted Permutation
ユーザー gew1fw
提出日時 2025-06-12 19:18:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,188 bytes
コンパイル時間 359 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 64,768 KB
最終ジャッジ日時 2025-06-12 19:18:29
合計ジャッジ時間 2,681 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
max_n = 2 * 10**5 + 10

# Precompute factorials and inverse factorials modulo MOD
fact = [1] * (max_n)
for i in range(1, max_n):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (max_n)
inv_fact[max_n-1] = pow(fact[max_n-1], MOD-2, MOD)
for i in range(max_n-2, -1, -1):
    inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

def comb(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    K = int(input[1])
    X = int(input[2])
    
    inv2 = (MOD + 1) // 2  # 499122177
    
    # Compute T = ((N-1)*N / 2) - (X-1) mod MOD
    if N >= 2:
        numerator = ( (N-1) % MOD ) * ( N % MOD ) % MOD
        numerator = numerator * inv2 % MOD
        T = ( numerator - (X-1) % MOD ) % MOD
    else:
        T = 0
    
    contribution_A = 0
    if K >= 2 and N >= 1:
        m = N - K + 1
        M = N - 1
        if m <= M:
            sum_terms = 0
            for j in range(m, M + 1):
                term = (j - 1) * fact[j] % MOD
                sum_terms = (sum_terms + term) % MOD
            fact_n_minus_3 = fact[N-3] if N >= 3 else 0
            contribution_A = T * fact_n_minus_3 % MOD
            contribution_A = contribution_A * sum_terms % MOD
        else:
            contribution_A = 0
    else:
        contribution_A = 0
    
    # Compute contribution_B
    contribution_B = 0
    if K >= 1:
        c = comb(N-2, K-1)
        term = (X-1) % MOD * c % MOD
        term = term * fact[K-1] % MOD
        fact_nk = fact[N-K] if N >= K else 0
        term = term * fact_nk % MOD
        term = term * fact_nk % MOD
        contribution_B = term
    else:
        contribution_B = 0
    
    # Compute contribution_C
    contribution_C = 0
    if N >= K:
        fact_n_1 = fact[N-1]
        fact_nk = fact[N-K] if N >= K else 0
        term = (fact_n_1 * (fact_nk - 1)) % MOD
        term = term * inv2 % MOD
        contribution_C = term
    else:
        contribution_C = 0
    
    total = (contribution_A + contribution_B + contribution_C) % MOD
    print(total)

if __name__ == "__main__":
    main()
0