結果

問題 No.1501 酔歩
ユーザー gew1fw
提出日時 2025-06-12 16:26:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,809 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 92,192 KB
最終ジャッジ日時 2025-06-12 16:27:21
合計ジャッジ時間 6,610 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    sys.setrecursionlimit(1 << 25)
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    if K == 1:
        print("0")
        return
    if K == N:
        print("1")
        return
    
    # Compute x_i for i from 2 to N-1
    x = [ (0, 1) ] * (N + 1)  # x[0], x[1] unused, x[2..N-1] are stored
    
    # Initialize x_2
    a_prev_num = A[0]
    a_prev_den = A[0] + A[2]
    b_prev_num = A[2]
    b_prev_den = a_prev_den
    x_num = b_prev_num
    x_den = a_prev_den
    g = math.gcd(x_num, x_den)
    x[2] = (x_num // g, x_den // g)
    
    for i in range(3, N):
        # i-th position in 1-based
        # A_{i-1} is A[i-2], A_{i+1} is A[i]
        a_i_num = A[i-2]
        a_i_den = A[i-2] + A[i]
        b_i_num = A[i]
        b_i_den = a_i_den
        
        x_prev_num, x_prev_den = x[i-1]
        
        denominator = a_i_den * x_prev_den - a_i_num * x_prev_num
        if denominator == 0:
            x_num = 0
            x_den = 1
        else:
            x_num = b_i_num * x_prev_den * a_i_den
            x_den = b_i_den * denominator
        
        g = math.gcd(x_num, x_den)
        x_num //= g
        x_den //= g
        x[i] = (x_num, x_den)
    
    # Compute the product from K to N-1
    product_num = 1
    product_den = 1
    for i in range(K, N):
        xi_num, xi_den = x[i]
        product_num *= xi_num
        product_den *= xi_den
        g = math.gcd(product_num, product_den)
        product_num //= g
        product_den //= g
    
    if product_num == 0:
        print("0")
    else:
        g = math.gcd(product_num, product_den)
        product_num //= g
        product_den //= g
        print(f"{product_num}/{product_den}")

if __name__ == "__main__":
    main()
0