結果

問題 No.2384 Permutations of Permutations
ユーザー qwewe
提出日時 2025-05-14 12:57:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,477 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 59,328 KB
最終ジャッジ日時 2025-05-14 12:59:11
合計ジャッジ時間 1,947 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    # Read input N and K
    N, K = map(int, sys.stdin.readline().split())
    
    # Define the modulus
    MOD = 998244353

    # Handle the base case N=2
    # For N=2, the symmetric group S_2 = {identity, (1 2)}. 
    # Since 2 <= K <= N, K must be 2.
    # The permutation f is defined as f(1)=2, f(2)=1, which is the transposition (1 2).
    # S_2 is isomorphic to the cyclic group of order 2, Z_2.
    # The only automorphism of Z_2 is the identity map. 
    # So the only automorphism F of S_2 is F(sigma) = sigma for all sigma in S_2.
    # We need to check if this F satisfies the condition F(f) = f.
    # F(f) = F((1 2)) = (1 2) = f. Yes, it satisfies the condition.
    # Therefore, there is exactly 1 such automorphism for N=2.
    if N == 2:
        print(1)
        return

    # For N >= 3, we need to compute the size of the centralizer of f in S_N, possibly multiplied by 2 for N=6.
    # The permutation f is the K-cycle (1 2 ... K), fixing elements K+1, ..., N.
    # Its cycle type is one cycle of length K and N-K fixed points (cycles of length 1).
    # The size of the centralizer C_{S_N}(f) is given by the formula: Product over k of (k^c_k * c_k!),
    # where c_k is the number of cycles of length k.
    # Here, c_K = 1, c_1 = N-K, and other c_k = 0.
    # |C_{S_N}(f)| = (K^1 * 1!) * (1^(N-K) * (N-K)!) = K * (N-K)!
    
    # We need to compute K * (N-K)! modulo MOD.
    
    # Calculate (N-K)! mod MOD
    # Initialize factorial result to 1 (for 0! = 1)
    fact_N_minus_K = 1
    
    # Compute (N-K)! iteratively modulo MOD.
    # The loop runs from 1 up to N-K.
    # If N-K = 0, the loop range is empty, fact_N_minus_K remains 1, which is correct for 0!.
    for i in range(1, N - K + 1):
        # Multiply by i and take modulo at each step to prevent overflow and keep numbers small.
        # Python's integers have arbitrary precision, so overflow isn't an issue unless numbers become excessively large,
        # but taking modulo frequently is good practice and necessary in languages with fixed-size integers.
        fact_N_minus_K = (fact_N_minus_K * i) % MOD

    # Calculate V = K * (N-K)! mod MOD
    # K can be up to N = 10^5. MOD is approx 10^9. K < MOD.
    # So K % MOD is just K.
    # We perform the multiplication and take the modulo.
    V = (K * fact_N_minus_K) % MOD

    # Determine the final answer based on N.
    
    # For N >= 3 and N != 6, all automorphisms of S_N are inner automorphisms.
    # An inner automorphism is F_g(h) = g * h * g^{-1} for some g in S_N.
    # The condition F(f) = f becomes F_g(f) = f, which means g * f * g^{-1} = f.
    # This is equivalent to g * f = f * g, meaning g commutes with f.
    # The number of such g is exactly the size of the centralizer of f, |C_{S_N}(f)|.
    # So for N >= 3, N != 6, the answer is V.
    
    ans = V
    
    # Handle the special case N=6
    # For N=6, S_6 has outer automorphisms. The group Aut(S_6) has index 2 over Inn(S_6).
    # The total number of automorphisms is 2 * |S_6| = 2 * 6!.
    # We need to count automorphisms F such that F(f) = f.
    # Inner automorphisms: The count is |C_{S_6}(f)| = V.
    # Outer automorphisms: An outer automorphism F maps f to F(f). The condition F(f)=f can hold
    # only if f and F(f) have the same cycle type.
    # Outer automorphisms of S_6 swap certain conjugacy classes (cycle types).
    # - K=2: f=(1 2), type (2,1^4). Maps to type (2,2,2). Different. Outer F cannot fix f.
    # - K=3: f=(1 2 3), type (3,1^3). Maps to type (3,3). Different. Outer F cannot fix f.
    # - K=4: f=(1 2 3 4), type (4,1^2). Maps to type (4,2). Different. Outer F cannot fix f.
    # - K=5: f=(1 2 3 4 5), type (5,1). Maps to type (5,1). Same type. Outer F might fix f.
    # - K=6: f=(1 2 3 4 5 6), type (6). Maps to type (6). Same type. Outer F might fix f.
    #
    # For K=5 and K=6, the cycle type is preserved. It turns out that the number of outer automorphisms
    # fixing f is also |C_{S_6}(f)| = V.
    # So the total count for N=6, K=5 or K=6 is V (inner) + V (outer) = 2V.
    if N == 6:
        if K == 5 or K == 6:
            # Total count is 2 * V for these K values when N=6.
            ans = (2 * V) % MOD
        # For K=2, 3, 4 when N=6, the answer remains V (only inner automorphisms contribute).
        # This is correctly handled because 'ans' was initialized to V.

    # Print the final answer
    print(ans)

# Call the solve function to run the logic
solve()
0