QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373428#5547. Short FunctionohwphilWA 6ms9688kbPython3777b2024-04-01 16:52:542024-04-01 16:52:55

Judging History

你现在查看的是最新测评结果

  • [2024-04-01 16:52:55]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:9688kb
  • [2024-04-01 16:52:54]
  • 提交

answer

import sys
MOD=119<<23|1
input=sys.stdin.readline
n,k=map(int,input().split())
*nums,=map(int,input().split())
cum_prod=[1]*(2*n+1)
for i in range(2*n):
    cum_prod[i+1]=(cum_prod[i]*nums[i%n])%MOD
def get_qr(p):
    global n
    # q는 mod MOD-1, r
    bq=1//n
    br=1%n
    accq=1//n
    accr=1%n
    while p:
        if p&1:
            bq=(bq*accq*n+br*accq+bq*accr)%(MOD-1)
            br=(br*accr)%n
        accq=(accq**2*n+2*accq*accr)%(MOD-1)
        accr**=2
        accr%=n
        p>>=1
        #print(bq,br,accq,accr)
    return (bq,br)
#print(get_qr(5))
    
cycle,out=get_qr(k)
ans=[pow(cum_prod[n],cycle,MOD)]*n
#print(cum_prod)
for i in range(n):
    ans[i]*=cum_prod[i+out]*pow(cum_prod[i],-1,MOD)
    ans[i]%=MOD
print(*ans)

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 9688kb

input:

5 2
1 2 3 4 5

output:

1 2 3 4 5

result:

wrong answer 1st numbers differ - expected: '24', found: '1'