結果
| 問題 |
No.1504 ヌメロニム
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:24 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,701 bytes |
| コンパイル時間 | 412 ms |
| コンパイル使用メモリ | 82,316 KB |
| 実行使用メモリ | 157,348 KB |
| 最終ジャッジ日時 | 2025-05-14 13:00:39 |
| 合計ジャッジ時間 | 5,922 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 24 TLE * 1 -- * 36 |
ソースコード
import sys
# Set higher recursion depth if needed, although the iterative NTT should be fine.
# sys.setrecursionlimit(2000)
def solve():
N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()
MOD = 998244353
# --- Utility functions START ---
def fast_pow(base, power):
"""Computes base^power % MOD efficiently using binary exponentiation."""
result = 1
while power > 0:
if power % 2 == 1:
result = (result * base) % MOD
base = (base * base) % MOD
power //= 2
return result
def inverse(a):
"""Computes modular multiplicative inverse using Fermat's Little Theorem.
Assumes MOD is a prime number and a is not divisible by MOD."""
return fast_pow(a, MOD - 2)
# --- Utility functions END ---
# --- NTT implementation START ---
# Use a standard primitive root for MOD 998244353
primitive_root = 3
def ntt(a, is_inverse):
"""Performs Number Theoretic Transform (NTT) in place on list 'a'.
'is_inverse' determines if forward or inverse transform is performed.
Input list 'a' must have length that is a power of 2."""
n = len(a)
if n == 1:
return
# Bit-reversal permutation: arranges elements in the order required for Cooley-Tukey
# This ensures elements accessed in butterfly operations are correctly paired.
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]
# Cooley-Tukey algorithm (iterative version)
k = 1 # Represents half the size of the DFT blocks being merged at the current level
while k < n:
# Calculate the principal N/2k-th root of unity for this level
# This is omega_{2k} = primitive_root ^ ((MOD - 1) / (2*k))
w_len = fast_pow(primitive_root, (MOD - 1) // (2 * k))
if is_inverse:
# For inverse NTT, use the inverse root of unity
w_len = inverse(w_len)
# Iterate through blocks of size 2k
for i in range(0, n, 2 * k):
w = 1 # Current power of the root of unity (omega_{2k}^j)
# Perform butterfly operations within the block [i, i + 2k - 1]
for j in range(k):
# Combine elements from the first half (i+j) and second half (i+j+k)
u = a[i + j]
v = (a[i + j + k] * w) % MOD
# Butterfly operation: DFT[i+j] = DFT_even[j] + omega^j * DFT_odd[j]
# DFT[i+j+k] = DFT_even[j] - omega^j * DFT_odd[j]
a[i + j] = (u + v) % MOD
a[i + j + k] = (u - v + MOD) % MOD # Use + MOD to ensure the result is positive
w = (w * w_len) % MOD # Update to the next power of root of unity
k *= 2 # Move to the next level (double the block size)
# Scale by 1/n if performing inverse NTT
if is_inverse:
inv_n = inverse(n)
for i in range(n):
a[i] = (a[i] * inv_n) % MOD
def multiply(p1, p2):
"""Multiplies two polynomials p1 and p2 represented as lists of coefficients using NTT."""
len1 = len(p1)
len2 = len(p2)
# Determine the size for NTT (must be a power of 2)
# The degree of the result polynomial is (len1-1) + (len2-1). Its length is len1+len2-1.
final_len = len1 + len2 - 1
n = 1
while n < final_len:
n <<= 1 # Find the smallest power of 2 >= final_len
# Pad polynomials with zeros to the required size n
p1_ntt = p1 + [0] * (n - len1)
p2_ntt = p2 + [0] * (n - len2)
# Perform forward NTT on both polynomials
ntt(p1_ntt, False)
ntt(p2_ntt, False)
# Pointwise multiplication in the frequency domain
res_ntt = [(p1_ntt[i] * p2_ntt[i]) % MOD for i in range(n)]
# Perform inverse NTT to get the result polynomial coefficients in the time domain
ntt(res_ntt, True)
# Return the resulting coefficients, truncated to the actual polynomial length
return res_ntt[:final_len]
# --- NTT implementation END ---
# Base case check: Numeronym is defined for strings of length 2 or more.
if N < 2:
print(0) # If N < 2, no subsequences satisfy the condition.
return
# Precompute factorials and their modular inverses up to N.
# Factorials are needed up to N for the second NTT step.
MAX_FAC = N + 1
fact = [1] * MAX_FAC
invfact = [1] * MAX_FAC
for i in range(1, MAX_FAC):
fact[i] = (fact[i - 1] * i) % MOD
# Compute inverse factorial N! first, then compute others using i! = (i+1)! / (i+1)
invfact[MAX_FAC - 1] = inverse(fact[MAX_FAC - 1])
for i in range(MAX_FAC - 2, -1, -1):
invfact[i] = (invfact[i + 1] * (i + 1)) % MOD
# === Step 1: Compute DP[d] using the first NTT ===
# DP[d] is the count of pairs (i, j) such that s_i='i', s_j='n', and j-i-1=d (or j-i=d+1).
# This can be found via convolution of two polynomials derived from S.
# Construct polynomials A'(x) and B'(x) based on positions of 'i' and 'n'.
# A'(x) = sum_{i=1..N} [s_i == 'i'] x^{N-i} (Coefficients represent 'i' positions, reversed)
# B'(x) = sum_{j=1..N} [s_j == 'n'] x^j (Coefficients represent 'n' positions)
# The coefficient of x^k in C'(x) = A'(x)B'(x) gives sum over pairs (i,j) where (N-i)+j = k, i.e., j-i = k-N.
# We need DP[d], which corresponds to j-i=d+1. So we need k-N = d+1, or k = N+d+1.
# DP[d] is the coefficient of x^{N+d+1} in C'(x).
A_coeffs = [0] * N # Represents polynomial derived from 'i' positions, max degree N-1
B_coeffs = [0] * (N + 1) # Represents polynomial derived from 'n' positions, max degree N
# Populate coefficients based on S. Use 0-based indexing for S.
for i in range(N): # Python index i corresponds to 1-based index i+1 in the problem statement
if S[i] == 'i':
# s_{i+1} == 'i', contributes term x^{N-(i+1)} = x^{N-1-i}
A_coeffs[N - 1 - i] = 1
for j in range(N): # Python index j corresponds to 1-based index j+1
if S[j] == 'n':
# s_{j+1} == 'n', contributes term x^{j+1}
B_coeffs[j + 1] = 1
# Compute C'(x) = A'(x) * B'(x) using NTT
C_prime_coeffs = multiply(A_coeffs, B_coeffs)
# Result C'(x) has degree (N-1) + N = 2N-1. Length of coefficient list is 2N.
# Extract DP[d] coefficients. DP[d] = coefficient of x^{N+d+1} in C'(x).
# M is the maximum possible value for k, which is N-2.
M = N - 2
if M < 0: # This case is covered by N < 2 check above, but good to be robust.
print(0)
return
# p[d] stores DP[d]. This is the coefficient list for polynomial P(y) = sum DP[d] * y^d.
p = [0] * (M + 1) # P(y) has degree up to M = N-2
for d in range(M + 1): # d ranges from 0 to N-2
target_idx = N + d + 1 # Index corresponds to exponent N+d+1
# Ensure index is within bounds of the computed coefficients list.
if target_idx < len(C_prime_coeffs):
p[d] = C_prime_coeffs[target_idx]
# If index out of bounds, coefficient is 0, which is the default value in p.
# === Step 2: Compute X_k using the second NTT ===
# X_k = sum_{d=k..M} DP[d] * C(d, k). This corresponds to evaluating P(y) at y=x+1.
# Let Q(x) = P(x+1) = sum q_k x^k. Then q_k = X_k.
# We use a convolution method to compute the coefficients q_k.
# The formula q_k * k! = sum_{i=k..M} (p_i * i!) * (c^{i-k} / (i-k)!) holds. Here c=1.
# q_k * k! = sum_{i=k..M} (p_i * i!) * (1 / (i-k)!)
# Let a_i = p_i * i! and b_j = 1 / j!. We need sum_{i=k..M} a_i * b_{i-k}.
# This is a convolution. Let B_rev(x) = sum b_{M-j} x^j = sum (1 / (M-j)!) x^j.
# The (M+k)-th coefficient of (sum a_i x^i) * B_rev(x) is sum_{i-j'=k} a_i b_{j'}, which is exactly q_k * k!.
# Prepare coefficients for the second convolution
# PolyA(x) = sum a_i x^i where a_i = p_i * i!
a = [0] * (M + 1)
for i in range(M + 1):
a[i] = (p[i] * fact[i]) % MOD
# PolyB(x) = sum b'_j x^j where b'_j = 1 / (M-j)!
b_prime = [0] * (M + 1)
for j in range(M + 1):
b_prime[j] = invfact[M - j] # M-j ranges from M down to 0. Valid indices.
PolyA = a
PolyB = b_prime
# Compute PolyC(x) = PolyA(x) * PolyB(x) using NTT
PolyC_coeffs = multiply(PolyA, PolyB)
# PolyC(x) has degree M + M = 2M. Length of coefficients list is 2M+1.
# Extract X_k values from PolyC_coeffs
# We know q_k * k! = CoefC_{M+k}. So X_k = q_k = CoefC_{M+k} / k! = CoefC_{M+k} * invfact[k].
X = [0] * (M + 1) # Stores values X_0, ..., X_M = X_{N-2}
for k in range(M + 1): # k ranges from 0 to N-2
target_idx = M + k # Index in PolyC_coeffs corresponds to exponent M+k
# Ensure index is within bounds.
if target_idx < len(PolyC_coeffs):
X[k] = (PolyC_coeffs[target_idx] * invfact[k]) % MOD
# If index out of bounds, coefficient is 0, so X[k] remains 0.
# === Step 3: Compute the final XOR sum ===
# Calculate the bitwise XOR sum of all computed X_k values.
final_xor_sum = 0
for k_val in X: # Iterate through the computed values X_0, ..., X_{N-2}
final_xor_sum ^= k_val # Bitwise XOR operation
print(final_xor_sum)
solve()