結果

問題 No.1762 🐙🐄🌲
ユーザー qwewe
提出日時 2025-05-14 13:21:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 63 ms / 4,000 ms
コード長 4,207 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 78,592 KB
最終ジャッジ日時 2025-05-14 13:23:32
合計ジャッジ時間 3,835 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 998244353

# Precompute small factorials and their inverses (for 1/j!, j up to 6)
small_fact = [1] * 7
small_inv_fact = [1] * 7
for i in range(1, 7):
    small_fact[i] = (small_fact[i-1] * i) % MOD

small_inv_fact[6] = pow(small_fact[6], MOD - 2, MOD)
for i in range(5, -1, -1): 
    small_inv_fact[i] = (small_inv_fact[i+1] * (i+1)) % MOD

# Global lists for large factorials and modular inverses 1/n
FACT = []
INV_FACT = []
INV_N_ARR = [] 

def nCr_mod(n, r):
    if r < 0 or r > n:
        return 0
    # Assumes FACT and INV_FACT are globally precomputed and filled
    num = FACT[n]
    den = INV_FACT[r] * INV_FACT[n-r] % MOD
    return num * den % MOD

def solve():
    global FACT, INV_FACT, INV_N_ARR

    N, P_count = map(int, sys.stdin.readline().split())

    if (N - 1) % 4 != 0:
        print(0)
        return

    # For N >= 2 (problem constraint), if (N-1)%4 == 0, then N must be >= 5.
    # For N=5: N_U=1, N_T=4. So N_U >= 1 and N_T >= 1.
    # (N_U-1)! and (N_T-1)! are well-defined (0! = 1).
    N_U = (N - 1) // 4
    N_T = (3 * N + 1) // 4

    if N_T < P_count: 
        print(0)
        return

    N_T_prime = N_T - P_count 
    S_prime = (N - 1) - 8 * P_count 
    
    if S_prime < 0: 
        print(0)
        return
    
    K = S_prime - N_T_prime 

    if K < 0: 
        print(0)
        return
    if K > 6 * N_T_prime: # Max sum of (d_i-1) where d_i-1 <= 6
        print(0)
        return
    
    h_K_val = 0
    if N_T_prime == 0: # No non-perfect Tako vertices
        if K == 0: # Their degree sum (S_prime) and (d_i-1) sum (K) must be 0
            h_K_val = 1
        else: 
            h_K_val = 0 # Cannot make non-zero sum K with 0 vertices
    else: # N_T_prime > 0
        h_dp = [0] * (K + 1)
        # Base case for recurrence: h_0 = 1
        # K can be 0 here if S_prime == N_T_prime (all non-perfect Takos have degree 1)
        h_dp[0] = 1 
        
        if K > 0:
            INV_N_ARR = [1] * (K + 1) # INV_N_ARR[0] is dummy
            if K >= 1: INV_N_ARR[1] = 1 # inv[1]=1
            for i in range(2, K + 1): # Compute 1/i mod MOD
                INV_N_ARR[i] = MOD - (MOD // i) * INV_N_ARR[MOD % i] % MOD
        
        for n_val in range(1, K + 1):
            current_sum_for_h_n = 0
            # Recurrence: h_n = (1/n) * sum_{j=1 to min(n,6)} ((N_T'+1)j - n) * (1/j!) * h_{n-j}
            for j_val in range(1, min(n_val, 6) + 1):
                term_coeff_val = (N_T_prime + 1) * j_val - n_val
                term_coeff_val = (term_coeff_val % MOD + MOD) % MOD # Ensure positive result
                
                term = term_coeff_val * small_inv_fact[j_val] % MOD
                term = term * h_dp[n_val - j_val] % MOD
                current_sum_for_h_n = (current_sum_for_h_n + term) % MOD
            
            h_dp[n_val] = current_sum_for_h_n * INV_N_ARR[n_val] % MOD
        h_K_val = h_dp[K]

    if h_K_val == 0: # If this specific coefficient is 0, total ways is 0
        print(0)
        return

    # Precompute factorials and inverse factorials up to N for combinations
    max_fact_val = N
    FACT = [1] * (max_fact_val + 1)
    INV_FACT = [1] * (max_fact_val + 1)

    for i in range(1, max_fact_val + 1):
        FACT[i] = (FACT[i-1] * i) % MOD
    
    INV_FACT[max_fact_val] = pow(FACT[max_fact_val], MOD - 2, MOD)
    for i in range(max_fact_val - 1, -1, -1): # INV_FACT[0] will be 1
        INV_FACT[i] = (INV_FACT[i+1] * (i+1)) % MOD

    # Final calculation
    term1_binom_N_NT = nCr_mod(N, N_T)
    term2_binom_NT_P = nCr_mod(N_T, P_count)

    term3_num = FACT[N_T - 1] * FACT[N_U - 1] % MOD
    
    inv_6_val = pow(6, MOD - 2, MOD) # 6^{-1}
    inv_6_pow_NU = pow(inv_6_val, N_U, MOD) # (6^{-1})^{N_U} = (6^{N_U})^{-1}
    
    fact_7_val = small_fact[6] * 7 % MOD # 7!
    inv_fact7_val = pow(fact_7_val, MOD - 2, MOD) # (7!)^{-1}
    inv_fact7_pow_P = pow(inv_fact7_val, P_count, MOD) # ((7!)^{-1})^{P} = ((7!)^P)^{-1}

    term3_den_inv = inv_6_pow_NU * inv_fact7_pow_P % MOD
    
    ans = term1_binom_N_NT
    ans = ans * term2_binom_NT_P % MOD
    ans = ans * term3_num % MOD
    ans = ans * term3_den_inv % MOD
    ans = ans * h_K_val % MOD
    
    print(ans)

solve()
0