結果

問題 No.1683 Robot Guidance
ユーザー LyricalMaestro
提出日時 2025-02-08 03:41:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 226 ms / 2,000 ms
コード長 2,435 bytes
コンパイル時間 353 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 107,392 KB
最終ジャッジ日時 2025-02-08 03:41:42
合計ジャッジ時間 5,991 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1683

MOD= 10 ** 9 + 7


class CombinationCalculator:
    """
    modを考慮したPermutation, Combinationを計算するためのクラス
    """    
    def __init__(self, size, mod):
        self.mod = mod
        self.factorial = [0] * (size + 1)
        self.factorial[0] = 1
        for i in range(1, size + 1):
            self.factorial[i] = (i * self.factorial[i - 1]) % self.mod
        
        self.inv_factorial = [0] * (size + 1)
        self.inv_factorial[size] = pow(self.factorial[size], self.mod - 2, self.mod)

        for i in reversed(range(size)):
            self.inv_factorial[i] = ((i + 1) * self.inv_factorial[i + 1]) % self.mod

    def calc_combination(self, n, r):
        if n < 0 or n < r or r < 0:
            return 0

        if r == 0 or n == r:
            return 1
        
        ans = self.inv_factorial[n - r] * self.inv_factorial[r]
        ans %= self.mod
        ans *= self.factorial[n]
        ans %= self.mod
        return ans
    
    def calc_permutation(self, n, r):
        if n < 0 or n < r:
            return 0

        ans = self.inv_factorial[n - r]
        ans *= self.factorial[n]
        ans %= self.mod
        return ans
        

def main():
    A, B, X, Y = map(int, input().split())

    if A < abs(X) + abs(Y):
        print(0)
        return
    
    k = A - (abs(X) + abs(Y))
    if k % 2 != 0:
        print(0)
        return
    k //= 2

    combi = CombinationCalculator(A + B, MOD)
    answer = 0
    for kx in range(k + 1):
        ky = k - kx

        if X >= 0:
            t1 = X + kx
            t3 = kx
        else:
            t1 = kx
            t3 = abs(X) + kx
    
        if Y >= 0:
            t2 = Y + ky
            t4 = ky
        else:
            t2 = ky
            t4 = abs(Y) + ky

        ans = 1
        x1 = B // 4
        if t1 > 0:
            ans *= combi.calc_combination(t1 + x1, t1)
            ans %= MOD

        x2 = (B - 1) // 4
        if t2 > 0:
            ans *= combi.calc_combination(t2 + x2, t2)
            ans %= MOD

        x3 = (B - 2) // 4
        if t3 > 0:
            ans *= combi.calc_combination(t3 + x3, t3)
            ans %= MOD

        x4 = (B - 3) // 4
        if t4 > 0:
            ans *= combi.calc_combination(t4 + x4, t4)
            ans %= MOD

        answer += ans
        answer %= MOD

    print(answer)






    



if __name__ == "__main__":
    main()
0