Submission #8554332
Source Code Expand
Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,M,*X = map(int,read().split())
MOD = 10 ** 9 + 7
def mult(a,b,c,d,e,f):
# (a+bx+cx^2)(d+ex+fx^2) modulo 1-4x+2x^2-x^3
a,b,c,d,e = a*d,a*e+b*d,a*f+b*e+c*d,b*f+c*e,c*f
b += e; c -= 4*e; d += 2*e; e = 0
a += d; b -= 4*d; c += 2*d; d = 0
a %= MOD; b %= MOD; c %= MOD
return a,b,c
# (1/x)^i modulo (1-4x+2x^2-x^3)
M = 10 ** 5
A1 = [0] * (M+1)
a,b,c = 1,0,0
for i in range(M+1):
A1[i] = (a,b,c)
a,b,c = b+4*a,c-2*a,a
a %= MOD; b %= MOD; c %= MOD
# (1/x)^Mi modulo (1-4x+2x^2-x^3)
A2 = [0] * (M+1)
a,b,c = 1,0,0
d,e,f = A1[M]
for i in range(M+1):
A2[i] = (a,b,c)
a,b,c = mult(a,b,c,d,e,f)
def power(n):
# (1/x)^n modulo (1-4x+2x^2-x^3)
q,r = divmod(n,M)
a,b,c = A1[r]
d,e,f = A2[q]
return mult(a,b,c,d,e,f)
X.append(N)
a,b,c = 0,1,1
prev_x = 0
for x in X:
a,b,c = mult(a,b,c,*power(x - prev_x))
b -= a; c -= a
prev_x = x
answer = a
print(answer)
Submission Info
Submission Time |
|
Task |
E - Placing Squares |
User |
maspy |
Language |
Python (3.4.3) |
Score |
1600 |
Code Size |
1092 Byte |
Status |
AC |
Exec Time |
693 ms |
Memory |
39208 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
305 ms |
34784 KB |
sample_02.txt |
AC |
304 ms |
34784 KB |
sample_03.txt |
AC |
309 ms |
34768 KB |
sample_04.txt |
AC |
311 ms |
34776 KB |
subtask_1_01.txt |
AC |
436 ms |
36068 KB |
subtask_1_02.txt |
AC |
340 ms |
35048 KB |
subtask_1_03.txt |
AC |
390 ms |
35800 KB |
subtask_1_04.txt |
AC |
526 ms |
37080 KB |
subtask_1_05.txt |
AC |
693 ms |
38668 KB |
subtask_1_06.txt |
AC |
692 ms |
38664 KB |
subtask_1_07.txt |
AC |
674 ms |
39208 KB |
subtask_1_08.txt |
AC |
671 ms |
38708 KB |
subtask_1_09.txt |
AC |
314 ms |
34772 KB |
subtask_1_10.txt |
AC |
309 ms |
34780 KB |
subtask_1_11.txt |
AC |
314 ms |
34804 KB |
subtask_1_12.txt |
AC |
309 ms |
34784 KB |
subtask_1_13.txt |
AC |
307 ms |
34740 KB |
subtask_1_14.txt |
AC |
314 ms |
34752 KB |
subtask_1_15.txt |
AC |
308 ms |
34752 KB |
subtask_1_16.txt |
AC |
310 ms |
34724 KB |
subtask_1_17.txt |
AC |
431 ms |
36112 KB |
subtask_1_18.txt |
AC |
601 ms |
37932 KB |
subtask_1_19.txt |
AC |
307 ms |
34784 KB |
subtask_1_20.txt |
AC |
664 ms |
38700 KB |
subtask_1_21.txt |
AC |
306 ms |
34780 KB |
subtask_1_22.txt |
AC |
307 ms |
34728 KB |
subtask_1_23.txt |
AC |
309 ms |
34668 KB |
subtask_1_24.txt |
AC |
308 ms |
34732 KB |
subtask_1_25.txt |
AC |
306 ms |
34780 KB |
subtask_1_26.txt |
AC |
313 ms |
34780 KB |
subtask_1_27.txt |
AC |
311 ms |
34728 KB |
subtask_1_28.txt |
AC |
307 ms |
34668 KB |
subtask_1_29.txt |
AC |
312 ms |
34732 KB |
subtask_1_30.txt |
AC |
307 ms |
34780 KB |