結果
| 問題 |
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 |
ソースコード
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()
qwewe