結果
| 問題 |
No.2136 Dice Calendar?
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,006 bytes |
| コンパイル時間 | 326 ms |
| コンパイル使用メモリ | 82,736 KB |
| 実行使用メモリ | 433,840 KB |
| 最終ジャッジ日時 | 2025-05-14 13:16:40 |
| 合計ジャッジ時間 | 22,536 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 TLE * 1 -- * 8 |
ソースコード
import sys
# Set higher recursion depth if needed, although this DP is iterative.
# sys.setrecursionlimit(2000)
# Define the modulus
MOD = 998244353
# Modular Exponentiation: Computes (base^power) % MOD efficiently
# Used for calculating modular inverse.
def fast_pow(base, power):
"""Computes base^power % MOD efficiently using binary exponentiation."""
result = 1
while power > 0:
# If power is odd, multiply result with base
if power % 2 == 1:
result = (result * base) % MOD
# Square the base and halve the power
base = (base * base) % MOD
power //= 2
return result
# Modular Inverse: Computes the modular multiplicative inverse of a modulo MOD
# Uses Fermat's Little Theorem, which requires MOD to be a prime number.
# The inverse of a is a^(MOD-2) % MOD.
def inverse(a):
"""Computes the modular inverse of a modulo MOD."""
return fast_pow(a, MOD - 2)
# Precompute Factorials and Inverse Factorials up to MAX_N
# N is at most 20 according to constraints.
MAX_N = 20
fact = [1] * (MAX_N + 1) # fact[i] will store i! % MOD
invfact = [1] * (MAX_N + 1) # invfact[i] will store (i!)^{-1} % MOD
# Calculate factorials iteratively: fact[i] = (i-1)! * i % MOD
for i in range(1, MAX_N + 1):
fact[i] = (fact[i-1] * i) % MOD
# Calculate inverse factorial for MAX_N using modular inverse function
# Need inverse(fact[MAX_N])
# Check if fact[MAX_N] % MOD is 0. Since MOD = 998244353 is large prime and MAX_N = 20, fact[MAX_N] will not be divisible by MOD.
invfact[MAX_N] = inverse(fact[MAX_N])
# Calculate inverse factorials downwards iteratively using the relation:
# (i!)^{-1} = ((i+1)! * (i+1)^{-1})^{-1} = (i+1)!^{-1} * (i+1)
# So invfact[i] = invfact[i+1] * (i+1) % MOD
for i in range(MAX_N - 1, -1, -1):
invfact[i] = (invfact[i+1] * (i + 1)) % MOD
# Function to calculate number of permutations for a multiset
# The multiset is represented by `counts_tuple`: (c1, c2, ..., c9) where ci is count of digit i.
# It computes N! / (c1! * c2! * ... * c9!) mod MOD, where N is the total number of elements (sum of counts).
def count_permutations(counts_tuple):
"""
Calculates the number of distinct permutations of a multiset defined by counts_tuple.
Result is computed modulo MOD.
"""
N = sum(counts_tuple) # Total number of items in the multiset.
# The problem constraints state N >= 1, so N will always be at least 1 for the final states.
# A check for N=0 is technically safe but not necessary given constraints.
if N == 0:
# This case should not be reached for the final calculation if N >= 1.
# Could return 1 for empty permutation, or 0 if context requires non-empty.
return 0
# Start with N! from the precomputed table.
term = fact[N]
# Divide by c_k! for each digit k=1..9. This is done by multiplying with the modular inverse of c_k!.
# The counts are for digits 1 through 9, stored at indices 0 through 8.
for k in range(9):
count_k = counts_tuple[k] # Get the count for digit k+1
# We need the inverse factorial of count_k. Ensure count_k is within precomputed range.
# Since count_k <= N <= MAX_N, this is guaranteed.
# Multiply term by invfact[count_k]
term = (term * invfact[count_k]) % MOD
return term
def solve():
"""Reads input, performs dynamic programming to find all possible multisets,
sums permutations for each multiset, and prints the total count modulo MOD."""
# Read the number of dice N
N = int(sys.stdin.readline())
# Read the face values for each of the N dice
S_raw = [] # Temporary storage for raw input faces
for _ in range(N):
S_raw.append(list(map(int, sys.stdin.readline().split())))
# Extract the distinct available values for each die.
# We only care about which distinct numbers can appear on top.
# D[i] will store the list of unique face values for the (i+1)-th die.
D = []
for i in range(N):
# Use set() to find unique values, then convert back to list() for iteration.
D.append(list(set(S_raw[i])))
# Dynamic Programming state using memory optimization.
# `prev_dp_states` stores the set of reachable 'counts tuples' after processing the previous die.
# A counts tuple is (c1, c2, ..., c9) where ck is the count of digit k.
prev_dp_states = set()
# Initialize DP state: Before any dice are considered (step 0), the only possible
# multiset is the empty set, represented by counts (0, 0, ..., 0).
# The tuple is hashable and can be added to a set.
prev_dp_states.add(tuple([0]*9))
# Iterate through each die from 1 to N.
for i in range(1, N + 1):
# `current_dp_states` will store the set of reachable counts tuples after considering die `i`.
current_dp_states = set()
# For each state (counts tuple) reachable using dice 1 to i-1:
for counts_tuple in prev_dp_states:
# Consider choosing each distinct value 'v' available on the current die 'i'.
# The distinct values for die 'i' are stored in D[i-1] (due to 0-based indexing of D).
for v in D[i-1]:
# Create the new state's counts tuple:
# Start with the previous counts tuple, convert to list for modification.
counts_list = list(counts_tuple)
# Increment the count for digit 'v'. Since digits are 1-9, index is v-1.
counts_list[v-1] += 1
# Convert the modified list back to a tuple to make it hashable.
new_counts_tuple = tuple(counts_list)
# Add the new state (counts tuple) to the set for the current step.
# Sets automatically handle duplicates.
current_dp_states.add(new_counts_tuple)
# After processing all previous states and values for die i, update the set of states.
# The states computed for step `i` become the 'previous' states for step `i+1`.
prev_dp_states = current_dp_states
# Final calculation: The total number of distinct integers is the sum of permutations
# for each unique multiset found. Distinct multisets yield disjoint sets of integers.
total_permutations = 0
# `prev_dp_states` now holds the set of all possible final counts tuples after processing all N dice.
final_states = prev_dp_states
# Iterate through each final state (counts tuple) representing a possible multiset.
for counts_tuple in final_states:
# Calculate the number of distinct permutations for this multiset.
perms = count_permutations(counts_tuple)
# Add this count to the total, modulo MOD.
total_permutations = (total_permutations + perms) % MOD
# Print the final total count.
print(total_permutations)
# Standard Python entry point check.
if __name__ == "__main__":
solve()