結果

問題 No.1839 Concatenation Matrix
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:17:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,265 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 267,896 KB
最終ジャッジ日時 2025-05-14 13:18:39
合計ジャッジ時間 6,845 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to read input faster
# Using sys.stdin.readline is generally faster than input()
input = sys.stdin.readline 

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # The modulus M
    MOD = 998244353
    # M-1 is used for Fermat's Little Theorem exponent reduction
    MOD_MINUS_1 = MOD - 1
    
    # X_curr stores the values X_{i, j} for the current step i.
    # Initially, it holds X_{1, j} = a_j for i=1.
    X_curr = list(A) 
    
    # We need to calculate P_i = 10^{L_{i-1}} mod MOD for each step i from 2 to N.
    # L_{i-1} is the length of numbers at step i-1, which is 2^{i-2}.
    # So we need P_i = 10^{2^{i-2} mod (MOD-1)} mod MOD.
    # We can precompute these P_i values.
    
    # P[i] will store the factor 10^{L_{i-1}} needed for step i.
    # The array is 1-indexed for convenience (index i corresponds to step i).
    P = [0] * (N + 1) 
    
    # current_exponent_val holds 2^{k} mod (MOD-1) iteratively.
    # Starts with k=0. This corresponds to the exponent needed for step i=2, which is L_1 = 2^{2-2} = 2^0 = 1.
    current_exponent_val = 1 
    
    # Calculate P_i values for i = 2 to N
    for i in range(2, N + 1):
        # The exponent needed for step i is 2^{i-2}.
        # current_exponent_val holds this value (modulo MOD-1).
        exponent_mod = current_exponent_val 
        
        # Calculate P_i = 10^exponent_mod mod MOD using modular exponentiation
        P[i] = pow(10, exponent_mod, MOD)
        
        # Update exponent for the next step (i+1): needs 2^{(i+1)-2} = 2^{i-1}.
        # This is the previous exponent value times 2.
        # We keep it modulo MOD-1 because it's used as an exponent.
        current_exponent_val = (current_exponent_val * 2) % MOD_MINUS_1

    
    # Perform the N-1 steps of the recurrence relation
    # X_{i,j} = (X_{i-1,j} * P_i + X_{i-1,j+1}) % MOD
    
    # We use two lists to manage states across steps: X_curr and X_next.
    # X_curr holds values from step i-1. X_next will hold values for step i.
    X_next = [0] * N 

    # Loop through steps i = 2 to N
    for i in range(2, N + 1):
        # Get the precomputed factor P_i for this step
        Pi = P[i]
        
        # Calculate X_next[j] for all j based on X_curr values
        for j in range(N):
            # Value X_{i-1, j} from the previous step
            current_val = X_curr[j]
            
            # Index for the next element X_{i-1, j+1}, wrapping around N.
            # If j = N-1, (j+1)%N = 0. This handles the cyclic behavior.
            next_val_idx = (j + 1) % N 
            next_val = X_curr[next_val_idx]
            
            # Apply the recurrence relation modulo MOD
            # X_{i,j} = (X_{i-1,j} * P_i + X_{i-1,j+1}) % MOD
            X_next[j] = (current_val * Pi + next_val) % MOD
        
        # Update X_curr for the next iteration.
        # Copy the contents of X_next to X_curr. Using slice assignment `[:]`
        # is efficient in Python for copying list contents.
        X_curr[:] = X_next 

    # After the loop finishes (i=N), X_curr holds the final values X_{N, j}.
    # Print each value on a new line.
    for val in X_curr:
        print(val)

# Call the main function to solve the problem
solve()
0