結果
| 問題 |
No.1195 数え上げを愛したい（文字列編）
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:11:38 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,141 bytes |
| コンパイル時間 | 155 ms |
| コンパイル使用メモリ | 82,652 KB |
| 実行使用メモリ | 274,364 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:28 |
| 合計ジャッジ時間 | 8,785 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 25 |
ソースコード
import sys
# Fast I/O for reading input
def input():
return sys.stdin.readline().strip()
# Define the modulus
MOD = 998244353
# Precompute factorials and inverse factorials up to the maximum possible length of S
# The problem states |S| <= 3 * 10^5
MAX_N_precompute = 3 * 10**5
# Initialize lists for factorials and inverse factorials
fact = [1] * (MAX_N_precompute + 1)
inv_fact = [1] * (MAX_N_precompute + 1)
def precompute_factorials(max_val):
"""
Precomputes factorials and inverse factorials modulo MOD up to max_val.
"""
# Compute factorials: fact[i] = i! mod MOD
for i in range(1, max_val + 1):
fact[i] = (fact[i-1] * i) % MOD
# Compute inverse factorial of max_val using modular exponentiation (Fermat's Little Theorem)
# inv_fact[max_val] = (max_val!)^(MOD-2) mod MOD
inv_fact[max_val] = pow(fact[max_val], MOD - 2, MOD)
# Compute inverse factorials downwards using the relation (k!)^{-1} = ((k+1)! )^{-1} * (k+1)
# This is more efficient than computing modular inverse for each k.
for i in range(max_val - 1, -1, -1):
inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD
# Call precomputation once with the maximum possible |S|
precompute_factorials(MAX_N_precompute)
# Iterative NTT (Number Theoretic Transform) implementation
# Based on standard Cooley-Tukey FFT algorithm adapted for modular arithmetic
def ntt_internal(a, inv):
"""
Performs NTT or Inverse NTT on the list `a`.
`inv` flag indicates if Inverse NTT is needed.
The list `a` is modified in-place.
Returns the transformed list.
"""
n = len(a)
if n == 1:
return a
# Bit-reversal permutation: rearrange elements to the order required by iterative FFT
# This ensures elements that combine in butterflies are adjacent at appropriate stages.
j = 0
for i in range(1, n):
bit = n >> 1
while j & bit:
j ^= bit
bit >>= 1
j ^= bit
if i < j:
a[i], a[j] = a[j], a[i]
# Main Cooley-Tukey butterfly loops
len_ = 2 # Current transform size (block size)
while len_ <= n:
# Calculate the principal len_-th root of unity modulo MOD
# Using primitive root 3 for MOD = 998244353
wlen = pow(3, (MOD - 1) // len_, MOD)
if inv:
# For inverse NTT, use the modular inverse of the root of unity
wlen = pow(wlen, MOD - 2, MOD)
# Iterate through blocks of size len_
i = 0
while i < n:
w = 1 # Current power of the root of unity wlen
# Perform butterfly operations within the block
for k in range(len_ // 2):
# Standard butterfly operation:
# u = a[i+k], v = a[i+k+len_/2] * w^k
# a[i+k] = u + v
# a[i+k+len_/2] = u - v
u = a[i + k]
v = (a[i + k + len_ // 2] * w) % MOD
a[i + k] = (u + v) % MOD
a[i + k + len_ // 2] = (u - v + MOD) % MOD # Add MOD to ensure result is non-negative
w = (w * wlen) % MOD # Update root power for next iteration
i += len_ # Move to the next block
len_ <<= 1 # Double the block size for the next level
# If performing inverse NTT, divide all resulting coefficients by n (modulo MOD)
if inv:
n_inv = pow(n, MOD - 2, MOD) # Modular inverse of n
for i in range(n):
a[i] = (a[i] * n_inv) % MOD
return a
# Polynomial multiplication using NTT
def poly_mult(a, b):
"""
Multiplies two polynomials represented by coefficient lists `a` and `b` using NTT.
Returns the coefficient list of the product polynomial.
"""
len_a = len(a)
len_b = len(b)
# Calculate the length required for the result polynomial coefficient list
# Degree of product is (len_a - 1) + (len_b - 1) = len_a + len_b - 2
# Number of coefficients is (degree + 1) = len_a + len_b - 1
res_len = len_a + len_b - 1
# Determine the NTT size: smallest power of 2 >= res_len
n = 1
while n < res_len:
n <<= 1
# Pad the coefficient lists with zeros to match the NTT size n
a_pad = a + [0] * (n - len_a)
b_pad = b + [0] * (n - len_b)
# Compute forward NTT for both polynomials
# ntt_internal modifies lists in-place, so pass copies if needed, though here it's fine.
a_ntt = ntt_internal(a_pad, False)
b_ntt = ntt_internal(b_pad, False)
# Perform pointwise multiplication in the frequency domain
c_ntt = [0] * n
for i in range(n):
c_ntt[i] = (a_ntt[i] * b_ntt[i]) % MOD
# Compute inverse NTT to get the coefficients of the product polynomial
c = ntt_internal(c_ntt, True)
# Return the resulting coefficients, truncated to the actual required length (res_len)
return c[:res_len]
# Main logic to solve the problem
def solve():
"""
Reads input string S, calculates the number of distinct strings formed by rearranging
subsets of its characters (at least one character), and prints the result modulo MOD.
"""
S = input()
N = len(S) # Length of the input string S
# Count frequencies of each character in S using a dictionary
counts = {}
for char in S:
counts[char] = counts.get(char, 0) + 1
# Get the list of counts for distinct characters present in S
distinct_counts = list(counts.values())
# Initialize the polynomial P(x) representing the overall Exponential Generating Function (EGF).
# Start with P(x) = 1 (coefficient list [1]), representing the base case (using an empty set of characters).
# The coefficient of x^j / j! in P(x) will represent the sum of ways to form strings of length j.
current_poly_coeffs = [1]
# Iteratively multiply the current EGF polynomial P(x) by the EGF for each distinct character count
for count_Ni in distinct_counts:
# Construct the polynomial A_i(x) for the current character count N_i.
# This polynomial represents the EGF for choosing k characters of this type (0 <= k <= N_i).
# A_i(x) = sum_{k=0}^{N_i} (1/k!) * x^k
# The coefficients are [1/0!, 1/1!, ..., 1/N_i!] obtained from precomputed inverse factorials.
poly_Ai_coeffs = [inv_fact[k] for k in range(count_Ni + 1)]
# Multiply the current overall EGF polynomial P(x) by A_i(x) using NTT based polynomial multiplication.
# The result updates P(x) to include combinations with the current character type.
current_poly_coeffs = poly_mult(current_poly_coeffs, poly_Ai_coeffs)
# Prune the resulting polynomial: the maximum length of strings formed is N = |S|.
# The polynomial degree cannot exceed N. If the resulting polynomial has degree > N (length > N+1),
# trim the coefficients corresponding to degrees greater than N.
if len(current_poly_coeffs) > N + 1:
current_poly_coeffs = current_poly_coeffs[:N+1]
# After processing all distinct characters, `current_poly_coeffs` holds the coefficients p_j of the final EGF P(x).
# P(x) = sum_{j=0}^{N} p_j x^j, where p_j = dp(m, j) / j!
# dp(m, j) is the sum of multinomial coefficients corresponding to strings of length j.
final_coeffs = current_poly_coeffs
# Calculate the final answer: sum of dp(m, j) for j = 1 to N.
# We need strings formed by at least one character, so sum starts from j=1.
total_sum = 0
# Iterate through possible string lengths j from 1 up to N.
# The loop upper bound must respect the actual length of `final_coeffs`.
max_j = min(N, len(final_coeffs) - 1) # Max index is len - 1
for j in range(1, max_j + 1):
# Get the coefficient p_j = final_coeffs[j]
# Compute dp(m, j) = p_j * j! using precomputed factorials
dp_m_j = (final_coeffs[j] * fact[j]) % MOD
# Add dp(m, j) to the total sum modulo MOD
total_sum = (total_sum + dp_m_j) % MOD
# Print the final result
print(total_sum)
# Execute the solver function
solve()