From c1008fe39217be7f91f0ea23483e747bfbc5743e Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Mon, 16 Dec 2019 21:13:07 +0700 Subject: The good, the bad and the ugly --- codechef/binxor.py | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100755 codechef/binxor.py (limited to 'codechef/binxor.py') diff --git a/codechef/binxor.py b/codechef/binxor.py new file mode 100755 index 0000000..6f87d56 --- /dev/null +++ b/codechef/binxor.py @@ -0,0 +1,28 @@ +#!/usr/bin/env python3 +from functools import reduce +from itertools import accumulate +from typing import Iterable, Iterator + +MOD = 1_000_000_007 +LENGTH = 100_001 + + +def add(x: int, y: int) -> int: return (x + y) % MOD +def mul(x: int, y: int) -> int: return x * y % MOD + + +def khalid(iterable: Iterable[int]) -> Iterator[int]: + yield 1 + yield from iterable + + +modinv = [pow(i, MOD-2, MOD) for i in range(1, LENGTH)] +facinv = tuple(khalid(accumulate(modinv, mul))) +fac = tuple(khalid(accumulate(range(1, LENGTH), mul))) + +for t in range(int(input())): + n = int(input()) + a, b = (min(b.count(c) for c in '01') + for b in (input() for i in range(2))) + print(reduce(add, (mul(mul(fac[n], facinv[i]), facinv[n - i]) + for i in range(abs(a-b), a+b+1, 2)))) -- cgit 1.4.1