AtCoder Beginner Contest 003

Submission #6909283

Source codeソースコード

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class FactInvMOD:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX:階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD

        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """
        if n < r: return 0
        # あり得ない状況が来たら0を返す
        if n < 0 or r < 0: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nPr(self, n, r):
        """ 順列 """
        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """
        # r個選ぶところにN-1個の仕切りを入れる
        return self.nCr(r+n-1, r)

_R, C = MAP()
X, Y = MAP()
D, L = MAP()
E = X * Y - D - L

fim = FactInvMOD(X*Y, MOD)

total = fim.nCr(X*Y, E) * fim.nCr(D+L, D) % MOD

# いずれかの辺が真っ白ならNG
# 横1辺
P = Q = fim.nCr(X*(Y-1), E-X) * fim.nCr(D+L, D) % MOD
# 縦1辺
R = S = fim.nCr((X-1)*Y, E-Y) * fim.nCr(D+L, D) % MOD
# 横2辺
PQ = fim.nCr(X*(Y-2), E-X*2) * fim.nCr(D+L, D) % MOD
# 縦2辺
RS = fim.nCr((X-2)*Y, E-Y*2) * fim.nCr(D+L, D) % MOD
# 縦横1辺ずつ
PR = PS = QR = QS = fim.nCr((X-1)*(Y-1), E-X-Y+1) * fim.nCr(D+L, D) % MOD
# 横2辺、縦1辺
PQR = PQS = fim.nCr((X-1)*(Y-2), E-X*2-Y+2) * fim.nCr(D+L, D) % MOD
# 横1辺、縦2辺
PRS = QRS = fim.nCr((X-2)*(Y-1), E-X-Y*2+2) * fim.nCr(D+L, D) % MOD
# 4辺全部
PQRS = fim.nCr((X-2)*(Y-2), E-X*2-Y*2+4) * fim.nCr(D+L, D) % MOD

# 包徐原理でNGなパターンの通り数を出す
ng = (P*2 + R*2 - PQ - RS - PR*4 + PQR*2 + PRS*2 - PQRS) % MOD
ok = (total - ng) % MOD

# 区画内での配置の通り数 * 部屋全体から区画を配置する通り数
print(ok*(_R-X+1)*(C-Y+1)%MOD)

Submission

Task問題 D - AtCoder社の冬
User nameユーザ名 Coki628
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 WA
Score得点 0
Source lengthソースコード長 3386 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
sub 0 / 100 00_sample_01E.txt,00_sample_02E.txt,00_sample_03E.txt,test_03E.txt,test_04E.txt,test_07E.txt,test_08E.txt,test_11E.txt,test_12E.txt,test_15E.txt,test_16E.txt,test_19E.txt,test_20E.txt,test_23E.txt,test_24E.txt,test_27E.txt,test_28E.txt,test_31E.txt,test_32E.txt,test_36E.txt,test_37E.txt,test_38E.txt,test_39E.txt,test_45E.txt,test_47E.txt
All 0 / 1 00_sample_01E.txt,00_sample_02E.txt,00_sample_03E.txt,00_sample_04.txt,test_01.txt,test_02.txt,test_03E.txt,test_04E.txt,test_05.txt,test_06.txt,test_07E.txt,test_08E.txt,test_09.txt,test_10.txt,test_11E.txt,test_12E.txt,test_13.txt,test_14.txt,test_15E.txt,test_16E.txt,test_17.txt,test_18.txt,test_19E.txt,test_20E.txt,test_21.txt,test_22.txt,test_23E.txt,test_24E.txt,test_25.txt,test_26.txt,test_27E.txt,test_28E.txt,test_29.txt,test_30.txt,test_31E.txt,test_32E.txt,test_33.txt,test_34.txt,test_35.txt,test_36E.txt,test_37E.txt,test_38E.txt,test_39E.txt,test_40.txt,test_41.txt,test_42.txt,test_43.txt,test_44.txt,test_45E.txt,test_46.txt,test_47E.txt,test_48.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01E.txt AC 18 ms 3316 KB
00_sample_02E.txt AC 18 ms 3316 KB
00_sample_03E.txt AC 18 ms 3316 KB
00_sample_04.txt AC 18 ms 3316 KB
test_01.txt AC 18 ms 3316 KB
test_02.txt AC 18 ms 3316 KB
test_03E.txt AC 18 ms 3316 KB
test_04E.txt AC 18 ms 3316 KB
test_05.txt AC 18 ms 3316 KB
test_06.txt AC 18 ms 3316 KB
test_07E.txt AC 18 ms 3316 KB
test_08E.txt AC 18 ms 3316 KB
test_09.txt AC 18 ms 3316 KB
test_10.txt AC 18 ms 3316 KB
test_11E.txt AC 18 ms 3316 KB
test_12E.txt AC 18 ms 3316 KB
test_13.txt AC 18 ms 3316 KB
test_14.txt AC 18 ms 3316 KB
test_15E.txt AC 18 ms 3316 KB
test_16E.txt AC 18 ms 3316 KB
test_17.txt AC 18 ms 3316 KB
test_18.txt AC 18 ms 3316 KB
test_19E.txt AC 18 ms 3316 KB
test_20E.txt AC 18 ms 3316 KB
test_21.txt AC 18 ms 3316 KB
test_22.txt AC 18 ms 3316 KB
test_23E.txt AC 18 ms 3316 KB
test_24E.txt AC 18 ms 3316 KB
test_25.txt AC 18 ms 3316 KB
test_26.txt AC 18 ms 3316 KB
test_27E.txt AC 18 ms 3316 KB
test_28E.txt AC 18 ms 3316 KB
test_29.txt AC 18 ms 3316 KB
test_30.txt AC 18 ms 3316 KB
test_31E.txt AC 18 ms 3316 KB
test_32E.txt AC 19 ms 3316 KB
test_33.txt AC 18 ms 3316 KB
test_34.txt AC 18 ms 3316 KB
test_35.txt AC 18 ms 3316 KB
test_36E.txt AC 18 ms 3316 KB
test_37E.txt AC 18 ms 3316 KB
test_38E.txt AC 18 ms 3316 KB
test_39E.txt WA
test_40.txt AC 18 ms 3316 KB
test_41.txt AC 18 ms 3316 KB
test_42.txt AC 18 ms 3316 KB
test_43.txt AC 18 ms 3316 KB
test_44.txt AC 18 ms 3316 KB
test_45E.txt AC 18 ms 3320 KB
test_46.txt AC 18 ms 3316 KB
test_47E.txt AC 18 ms 3316 KB
test_48.txt AC 18 ms 3316 KB