| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 561965 |
2022-05-14T01:41:08 Z |
jh05013 |
목공 (kriii4_A) |
PyPy 3 |
|
2369 ms |
30420 KB |
MOD = 1092616193
proot = 3
iproot = pow(proot, MOD-2, MOD)
def NTT(N, X, di):
j = 0
for i in range(1, N):
k = N>>1
while j >= k: j-= k; k>>= 1
j+= k
if i<j: X[i], X[j] = X[j], X[i]
i = 1
while i < N:
x = pow(iproot if di else proot, MOD//i>>1, MOD); j = 0
while j < N:
y = 1
for k in range(i):
z = X[i|j|k]*y%MOD; X[i|j|k]= X[j|k]-z
if X[i|j|k] < 0: X[i|j|k]+= MOD
X[j|k]+= z
if X[j|k] >= MOD: X[j|k]-= MOD
y = y*x%MOD
j+= i<<1
i<<= 1
if di:
j = pow(N, MOD-2, MOD)
for i in range(N): X[i] = X[i]*j%MOD
def poly_mul(P, Q):
N = 1
while len(P)+len(Q) > N: N<<= 1
P = P[:]; Q = Q[:]
for L in P, Q: L.extend([0]*(N-len(L)))
NTT(N, P, 0); NTT(N, Q, 0)
for i in range(N): P[i] = P[i]*Q[i] % MOD
NTT(N, P, 1)
while P and P[-1] == 0: P.pop()
return P
# coeff of x^n in P/Q
def bm_onecoeff(P, Q, n):
while n >= 1:
Qm = [(x*(-1)**i)%MOD for i,x in enumerate(Q)]
P = poly_mul(P, Qm)[n%2::2]
Q = poly_mul(Q, Qm)[::2]
n>>= 1
return P[0] * pow(Q[0], MOD-2, MOD) % MOD
# n-th term of linear recurrence; next term is sum C[i]*ini[i]
def bostan_mori(C, ini, n):
while C and C[-1] == 0: C.pop()
if not C: return 0
Q = [1%MOD]+[(-x)%MOD for x in reversed(C)]
P = poly_mul(ini, Q)[:len(ini)]
return bm_onecoeff(P, Q, n)
MIS = lambda: map(int,input().split())
n, m = MIS()
q = [int(input()) for i in range(n)]
idenom = pow(sum(q), MOD-2, MOD)
q = [x*idenom%MOD for x in q]
C = [-q[0]] + [q[i]-q[i+1] for i in range(len(q)-1)] + [q[-1]+1]
print(bostan_mori(C, [0]*n+[1], m))
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
22888 KB |
Output is correct |
| 2 |
Correct |
143 ms |
23836 KB |
Output is correct |
| 3 |
Correct |
159 ms |
23224 KB |
Output is correct |
| 4 |
Correct |
140 ms |
23548 KB |
Output is correct |
| 5 |
Correct |
138 ms |
24328 KB |
Output is correct |
| 6 |
Correct |
138 ms |
22968 KB |
Output is correct |
| 7 |
Correct |
138 ms |
22568 KB |
Output is correct |
| 8 |
Correct |
149 ms |
23696 KB |
Output is correct |
| 9 |
Correct |
156 ms |
22936 KB |
Output is correct |
| 10 |
Correct |
138 ms |
22388 KB |
Output is correct |
| 11 |
Correct |
171 ms |
24052 KB |
Output is correct |
| 12 |
Correct |
148 ms |
23324 KB |
Output is correct |
| 13 |
Correct |
158 ms |
23036 KB |
Output is correct |
| 14 |
Correct |
157 ms |
24232 KB |
Output is correct |
| 15 |
Correct |
151 ms |
22476 KB |
Output is correct |
| 16 |
Correct |
156 ms |
22988 KB |
Output is correct |
| 17 |
Correct |
149 ms |
23376 KB |
Output is correct |
| 18 |
Correct |
169 ms |
24004 KB |
Output is correct |
| 19 |
Correct |
116 ms |
21904 KB |
Output is correct |
| 20 |
Correct |
120 ms |
21188 KB |
Output is correct |
| 21 |
Correct |
148 ms |
24032 KB |
Output is correct |
| 22 |
Correct |
149 ms |
23580 KB |
Output is correct |
| 23 |
Correct |
153 ms |
22644 KB |
Output is correct |
| 24 |
Correct |
149 ms |
22632 KB |
Output is correct |
| 25 |
Correct |
187 ms |
23144 KB |
Output is correct |
| 26 |
Correct |
127 ms |
22592 KB |
Output is correct |
| 27 |
Correct |
153 ms |
23196 KB |
Output is correct |
| 28 |
Correct |
191 ms |
23604 KB |
Output is correct |
| 29 |
Correct |
125 ms |
23436 KB |
Output is correct |
| 30 |
Correct |
122 ms |
23328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2316 ms |
30420 KB |
Output is correct |
| 2 |
Correct |
2197 ms |
30052 KB |
Output is correct |
| 3 |
Correct |
2369 ms |
29804 KB |
Output is correct |
| 4 |
Correct |
2251 ms |
30352 KB |
Output is correct |
| 5 |
Correct |
2209 ms |
29948 KB |
Output is correct |
| 6 |
Correct |
2323 ms |
30416 KB |
Output is correct |
| 7 |
Correct |
2269 ms |
29828 KB |
Output is correct |
| 8 |
Correct |
2263 ms |
30132 KB |
Output is correct |
| 9 |
Correct |
2185 ms |
30048 KB |
Output is correct |
| 10 |
Correct |
2211 ms |
29984 KB |
Output is correct |
| 11 |
Correct |
2041 ms |
29872 KB |
Output is correct |
| 12 |
Correct |
2041 ms |
29740 KB |
Output is correct |
| 13 |
Correct |
2158 ms |
29576 KB |
Output is correct |
| 14 |
Correct |
2290 ms |
29724 KB |
Output is correct |
| 15 |
Correct |
2075 ms |
29932 KB |
Output is correct |
| 16 |
Correct |
2219 ms |
29736 KB |
Output is correct |
| 17 |
Correct |
1105 ms |
29660 KB |
Output is correct |
| 18 |
Correct |
1115 ms |
29560 KB |
Output is correct |
| 19 |
Correct |
1171 ms |
29540 KB |
Output is correct |
| 20 |
Correct |
1145 ms |
29392 KB |
Output is correct |
