QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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)
Details
Tip: Click on the bar to expand more detailed information
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'