結果
| 問題 |
No.2243 Coaching Schedule
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:10:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,215 bytes |
| コンパイル時間 | 413 ms |
| コンパイル使用メモリ | 81,792 KB |
| 実行使用メモリ | 110,848 KB |
| 最終ジャッジ日時 | 2025-05-14 13:12:58 |
| 合計ジャッジ時間 | 6,193 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 5 TLE * 1 -- * 31 |
ソースコード
import sys
# Set higher recursion depth if needed, although this iterative solution doesn't require deep recursion.
# sys.setrecursionlimit(200000)
def solve():
# Read M (number of fields) and N (number of friends)
M, N = map(int, sys.stdin.readline().split())
# Handle the edge case where there are no friends.
# If N=0, no schedule is possible involving friends. The problem asks for combinations of N friends' schedules.
# If N=0, the only interpretation is 0 ways.
if N == 0:
print(0)
return
# Read the expert fields A_i for each friend i
A = list(map(int, sys.stdin.readline().split()))
# Define the modulus
MOD = 998244353
# Count the number of friends expert in each field
counts = {}
for x in A:
counts[x] = counts.get(x, 0) + 1
# Create a list C containing the counts of friends for each field that has at least one expert.
# This list C effectively captures the values C_f for fields f where C_f > 0.
C = list(counts.values())
# Calculate C_max = maximum number of friends expert in the same field.
# This determines the minimum number of days K required.
C_max = 0
# Check if C is non-empty ensures we don't call max on an empty list if N>0 but somehow A was empty (which constraints technically prevent).
if C:
# Find the maximum value in the list of counts C
# Using a loop instead of max() to avoid issues with empty list just in case, though constraints should ensure C is not empty if N>0.
for count in C:
if count > C_max:
C_max = count
# A valid schedule must use K days, where K >= C_max.
# Also, we cannot use more days than the number of friends N, since each friend teaches on exactly one day and each day must have at least one friend teaching.
# Therefore, K must be in the range [C_max, N]. If C_max > N, no such K exists.
if C_max > N:
print(0) # Impossible to schedule, print 0 ways.
return
# Precompute factorials and inverse factorials modulo MOD.
# We need factorials up to N+1 for combinations C(N+1, j).
# We need factorials up to N for computing W_j which involves fact[j].
MAX_FAC = N + 2 # Max index needed is N+1, so size N+2.
fact = [1] * MAX_FAC
inv_fact = [1] * MAX_FAC
for i in range(1, MAX_FAC):
fact[i] = (fact[i-1] * i) % MOD
# Compute inverse factorial of the largest factorial using Fermat's Little Theorem (pow(a, MOD-2, MOD))
inv_fact[MAX_FAC-1] = pow(fact[MAX_FAC-1], MOD - 2, MOD)
# Compute other inverse factorials iteratively using inv_fact[i] = inv_fact[i+1] * (i+1)
for i in range(MAX_FAC - 2, -1, -1):
inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD
# Modular combination function nCr = n! / (r! * (n-r)!) mod MOD
def nCr_mod(n, r):
# Handle invalid inputs for r
if r < 0 or r > n:
return 0
# Base cases for efficiency
if r == 0 or r == n:
return 1
# Optimization: use symmetry C(n, r) = C(n, n-r)
if r > n // 2:
r = n - r
# Calculate nCr using precomputed factorials and inverse factorials
num = fact[n]
den = (inv_fact[r] * inv_fact[n-r]) % MOD
return (num * den) % MOD
# W_j computation: Calculate W_j for j from C_max to N.
# W_j = product_{cf in C} P(j, cf), where P(j, cf) = j! / (j-cf)!
# This calculation could be slow: O(N * M_present) where M_present = len(C).
# In worst case M_present = N, leading to O(N^2) complexity.
# Accepted solution suggests this complexity might pass test cases.
W = [0] * (N + 1)
term_count = len(C) # Number of distinct fields represented among friends (M_present)
# Calculate W_j using the formula: W_j = (fact[j]^term_count) * product_{cf in C} inv_fact[j-cf]
for j in range(C_max, N + 1):
# Check if P(j, cf) is defined for all cf in C. This requires j >= cf.
possible = True
for cf in C:
if j < cf:
possible = False
break
# If j < cf for any cf, P(j, cf) = 0, so W_j = 0.
if not possible:
# W[j] remains 0 implicitly
continue
# Calculate W_j if possible
# Term 1: (fact[j] ^ term_count) mod MOD
term1 = pow(fact[j], term_count, MOD)
# Term 2: product_{cf in C} (inv_fact[j-cf]) mod MOD
term2 = 1
for cf in C:
# The index j-cf is guaranteed >= 0 due to the 'possible' check
term2 = (term2 * inv_fact[j-cf]) % MOD
# Combine terms to get W_j
W[j] = (term1 * term2) % MOD
# S_j computation: Calculate S_j for j from 0 to N using recurrence relation. O(N) complexity.
S = [0] * (N + 1)
# Calculate modular inverse of 2 needed for the recurrence
MOD_INV_2 = pow(2, MOD - 2, MOD)
# Base case S[0] depends on the parity of N
if N % 2 == 0:
S[0] = 1
else:
S[0] = 0
# Compute S_j for j=1..N using the recurrence:
# S_j = (S_{j-1} + (-1)^{N-j} * C(N+1, j)) / 2 mod MOD
for j in range(1, N + 1):
# Calculate the binomial coefficient C(N+1, j) mod MOD
term_binom = nCr_mod(N + 1, j)
# Determine the sign (-1)^(N-j) based on the parity of N-j
if (N - j) % 2 == 1: # If exponent is odd, sign is -1
# S[j-1] - C(N+1, j) mod MOD. Add MOD to ensure result is non-negative.
term_recur = (S[j-1] - term_binom + MOD) % MOD
else: # If exponent is even, sign is +1
# S[j-1] + C(N+1, j) mod MOD
term_recur = (S[j-1] + term_binom) % MOD
# Calculate S[j] = term_recur / 2 mod MOD (multiply by modular inverse of 2)
S[j] = (term_recur * MOD_INV_2) % MOD
# Final Summation: Compute the total number of ways. O(N) complexity.
# Total = Sum_{j=C_max..N} W[j] * S[j] mod MOD
total_sum = 0
for j in range(C_max, N + 1):
total_sum = (total_sum + W[j] * S[j]) % MOD
# Print the final result
print(total_sum)
# Execute the solve function
solve()