結果

問題 No.1501 酔歩
ユーザー Navier_BoltzmannNavier_Boltzmann
提出日時 2023-07-30 15:36:40
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 816 bytes
コンパイル時間 430 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 92,560 KB
最終ジャッジ日時 2024-10-09 10:49:43
合計ジャッジ時間 8,447 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 RE * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import *
from itertools import *
from functools import *
from heapq import *
import sys,math
input = sys.stdin.readline

N,K = map(int,input().split())
A = list(map(int,input().split()))
if N==1:
    print('1/1')
    exit()
if K==1:
    print(0)
    exit()
val = [(-1,-1) for _ in range(N)]
val[1] = (1,1)
val[0] = (0,1)
def f(x):
    if val[x]!=(-1,-1):
        return val[x]
    
    p1,q1 = f(x-1)
    p0,q0 = f(x-2)
    lx,ly = A[x]+A[x-2],A[x]
    rx,ry = A[x-2],A[x]
    ax,ay = lx*p1,ly*q1
    bx,by = rx*p0,ry*q0
    s = ax*by - bx*ay
    t = ay*by
    g = math.gcd(s,t)
    val[x] = (s//g,t//g)
    return val[x]
pn,qn = f(N-1)

pk,qk = f(K-1)
s = pk*qn
t = pn*qk
g = math.gcd(s,t)
s //=g
t //=g
print(str(s)+'/'+str(t))
0