Barcode is a combinatorics problem from the ICPC Asia Regional in Ho Chi Minh City 2017.

Problem

Here’s the link: https://open.kattis.com/problems/barcode

In this problem, we are asked to compute the number of valid barcodes where each bar is either blue or red and at least one of the following conditions hold.

1. No two blue bars can be next to each other.
2. The number of blue bars = the number of red bars.

We’re given T test cases, each test case consisting of integers N and M where

1 <= N <= 10^6

1 < M <= 10^7 and M is prime.

For each test case we want to compute the number of valid barcodes for a barcode of length N mod M

Approach

We can approach this problem in cases.

Case 1: No 2 consecutive blue bars

For a barcode of length N, we first count the number of barcodes that have no 2 consecutive blue bars. We call this function F(n). Consider the last bar in the barcode. It can be either red or blue. If it is red, there are F(n - 1) ways to select the rest of the bars. If the last bar is blue, the second to last bar must be red. Otherwise we will have 2 consecutive blue bars. Since, the second to last bar is now fixed, we have F(n - 2) ways to choose the rest of the bars. Therefore,

F(n) = F(n - 1) + F(n - 2)

Case 2: Number of blue bars = Number of red bars

We now count the number of barcodes that have the same number of red and blue bars. We first point out that this can’t be possible if the total number of bars is odd. This a simple combination. We have N spots and we want to choose N / 2 spots to be blue and N / 2 spots to be red. So this total is just

(N choose (N / 2))

Overcount

Notice we overcount barcodes where both case 1 and case 2 apply. Therefore, by the inclusion exclusion principle, we can simply count the number of barcodes that satisfy both cases and subtract it from total.

This is relatively simple to count. We have N / 2 blue bars and N / 2 red bars. We can take the N / 2 blue bars and put a red bar in between each of them, using up N / 2 - 1 red bars. We have just 1 red bar left. There are N / 2 + 1 places to place that one extra bar (in between any pair of adjacent blue bars or on the edges). Therefore, the overlap of the two cases is:

N / 2 + 1

Coding it Up

Coding up the combination is a little tricky because we are calculating it mod m which means that we cannot do integer division. Therefore, we do modular division by multiplying by the inverse using Fermat’s Little Theorem as follows.

# factorial modulo m
def fact(n, m):
    if n == 0:
        return 1
    return (n * fact(n - 1)) % m

# inverse modulo m
def inverse(n, m):
    return pow(n, m - 2, m)

# nCr modulo m
def nCr(a, b, m):
    return (fact(a, m) * inverse(fact(b, m)) * inverse(fact(a - b, m))) % m

Turns out this doesn’t work in the case where fact(a, m) is 0 and either fact(b, m) or fact(a - b, m) is 0. In this case we end up with a division of 0 by 0 which is undefined. To fix this we can count the number of times m divides the numerator in the combination and the number of times m divides the denominator in the combination. If these counts are not equal, the answer is 0. Otherwise, we can remove the m multiplicty from our factorials before proceeding with the computation of the combination. Code for this is below:

def modfact(a, n):
    x = 1
    for i in range(1, a + 1):
        while i % n == 0:
            i //= n
        x = (x * i) % n
    return x

def count(num, mod):
    total = 0
    cur = mod
    while num >= cur:
        total += num // cur
        cur *= mod
    return total

def nCr(a, b, n):
    if count(a, n) > (count(b, n) + count(a - b, n)):
        return 0
    fa = modfact(a, n)
    fb = modfact(b, n)
    fc = modfact(a - b, n)
    r = (fa * pow(fb, n - 2, n) * pow(fc, n - 2, n)) % n
    return r

From this, we can easily compute the answer using the formula from the approach section.

def solve():
    n, m = map(int, input().strip().split())
    a, b = 1, 1
    for _ in range(n):
        a, b = b, (a + b) % m
    if n % 2 == 0:
        b += nCr(n, n // 2, m)
        b -= n // 2 + 1
        b %= m
    print(b)