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
AC × 4
AC × 38
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