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 Python3 (3.4.3)
Score 1600
Code Size 1092 Byte
Status
Exec Time 693 ms
Memory 39208 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All 1600 / 1600 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 305 ms 34784 KB
sample_02.txt 304 ms 34784 KB
sample_03.txt 309 ms 34768 KB
sample_04.txt 311 ms 34776 KB
subtask_1_01.txt 436 ms 36068 KB
subtask_1_02.txt 340 ms 35048 KB
subtask_1_03.txt 390 ms 35800 KB
subtask_1_04.txt 526 ms 37080 KB
subtask_1_05.txt 693 ms 38668 KB
subtask_1_06.txt 692 ms 38664 KB
subtask_1_07.txt 674 ms 39208 KB
subtask_1_08.txt 671 ms 38708 KB
subtask_1_09.txt 314 ms 34772 KB
subtask_1_10.txt 309 ms 34780 KB
subtask_1_11.txt 314 ms 34804 KB
subtask_1_12.txt 309 ms 34784 KB
subtask_1_13.txt 307 ms 34740 KB
subtask_1_14.txt 314 ms 34752 KB
subtask_1_15.txt 308 ms 34752 KB
subtask_1_16.txt 310 ms 34724 KB
subtask_1_17.txt 431 ms 36112 KB
subtask_1_18.txt 601 ms 37932 KB
subtask_1_19.txt 307 ms 34784 KB
subtask_1_20.txt 664 ms 38700 KB
subtask_1_21.txt 306 ms 34780 KB
subtask_1_22.txt 307 ms 34728 KB
subtask_1_23.txt 309 ms 34668 KB
subtask_1_24.txt 308 ms 34732 KB
subtask_1_25.txt 306 ms 34780 KB
subtask_1_26.txt 313 ms 34780 KB
subtask_1_27.txt 311 ms 34728 KB
subtask_1_28.txt 307 ms 34668 KB
subtask_1_29.txt 312 ms 34732 KB
subtask_1_30.txt 307 ms 34780 KB