Submission #8554800


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

X = list(map(int,readline().split()))
Y = list(map(int,readline().split()))

for i in [1,3,5]:
    X[i] += 1
    Y[i] += 1

X1 = X[:2]; X2 = X[2:4]; X3 = X[4:]
Y1 = Y[:2]; Y2 = Y[2:4]; Y3 = Y[4:]

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 2 * 10 ** 6 + 10
MOD = 10**9 + 7
fact, fact_inv = make_fact(U,MOD)

answer = 0
for p in itertools.product([0,1],repeat=6):
    x1,x2,x3,y1,y2,y3 = [A[i] for A,i in zip([X1,X2,X3,Y1,Y2,Y3],p)]
    sgn = (-1) ** sum(p)
    a,b,c,d = x2-x1, x3-x2, x2-x1+y2-y1, x3-x2+y3-y2
    c += 2; d += 2; sgn = -sgn
    # (1+A)^c(1+B)^d / (A-B)^2 における A^aB^b の係数
    # まずはa+b+2次式部分を抽出する:A側の次数で持つ
    D = a + b + 2
    # A^i B^j の寄与。
    L = max(0, D-d)
    R = min(c, D)
    if L > R:
        continue
    x = fact[c] * fact_inv[L:R+1] % MOD * fact_inv[c-R:c-L+1][::-1] % MOD
    L,R = D-R,D-L
    y = fact[d] * fact_inv[L:R+1] % MOD * fact_inv[d-R:d-L+1][::-1] % MOD
    x *= y[::-1]
    x %= MOD
    # B=1と見立てる。(1-A)^2 で割って、A^(a-L)の係数
    np.cumsum(x,out=x)
    x %= MOD
    np.cumsum(x,out=x)
    x %= MOD
    L,R = D-R,D-L
    if 0 <= a-L < len(x):
        answer += sgn * x[a-L]

answer %= MOD
print(answer)

Submission Info

Submission Time
Task E - Sightseeing Plan
User maspy
Language Python (3.4.3)
Score 1600
Code Size 1926 Byte
Status AC
Exec Time 3886 ms
Memory 114048 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 3
AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.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
Case Name Status Exec Time Memory
sample_01.txt AC 433 ms 92212 KB
sample_02.txt AC 360 ms 90524 KB
sample_03.txt AC 3886 ms 107880 KB
subtask_1_01.txt AC 359 ms 90524 KB
subtask_1_02.txt AC 688 ms 90524 KB
subtask_1_03.txt AC 2780 ms 105232 KB
subtask_1_04.txt AC 359 ms 90524 KB
subtask_1_05.txt AC 361 ms 92572 KB
subtask_1_06.txt AC 691 ms 90612 KB
subtask_1_07.txt AC 1288 ms 91028 KB
subtask_1_08.txt AC 359 ms 90524 KB
subtask_1_09.txt AC 359 ms 90524 KB
subtask_1_10.txt AC 3506 ms 107408 KB
subtask_1_11.txt AC 3522 ms 109292 KB
subtask_1_12.txt AC 3530 ms 104464 KB
subtask_1_13.txt AC 3816 ms 100880 KB
subtask_1_14.txt AC 3667 ms 99348 KB
subtask_1_15.txt AC 3787 ms 102928 KB
subtask_1_16.txt AC 3837 ms 105492 KB
subtask_1_17.txt AC 3738 ms 102032 KB
subtask_1_18.txt AC 2954 ms 98024 KB
subtask_1_19.txt AC 362 ms 90524 KB
subtask_1_20.txt AC 3339 ms 114048 KB
subtask_1_21.txt AC 362 ms 90524 KB
subtask_1_22.txt AC 2942 ms 107280 KB
subtask_1_23.txt AC 3019 ms 108048 KB
subtask_1_24.txt AC 2958 ms 104848 KB