QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373420 | #5547. Short Function | ohwphil | WA | 9ms | 9636kb | Python3 | 726b | 2024-04-01 16:45:02 | 2024-04-01 16:45:02 |
Judging History
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=0
br=1
accq=2//n
accr=2%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
return (bq,br)
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)
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 9572kb
input:
5 2 1 2 3 4 5
output:
24 120 60 40 30
result:
ok 5 number(s): "24 120 60 40 30"
Test #2:
score: -100
Wrong Answer
time: 9ms
memory: 9636kb
input:
8 3 12 5 16 14 10 6 9 2
output:
1 1 1 1 1 1 1 1
result:
wrong answer 1st numbers differ - expected: '14515200', found: '1'