Dominoes (Codeforces 1608D)
Tags: Math, fft

You are given $$$n$$$ dominoes. Each domino has a left and a right cell. Each cell can be colored either black or white. Some cells are already colored, while some aren't yet.The coloring is said to be valid if and only if it is possible to rearrange the dominoes in some order such that for each $$$1 \le i \le n$$$ the color of the right cell of the $$$i$$$-th domino is different from the color of the left cell of the $$$((i \bmod n)+1)$$$-st domino. Note that you can't rotate the dominoes, so the left cell always remains the left cell, and the right cell always remains the right cell.Count the number of valid ways to color the yet uncolored cells of dominoes. Two ways are considered different if there is a cell that is colored white in one way and black in the other. In particular, colorings BW WB and WB BW different (and both invalid).As this number can be very big, output it modulo $$$998\,244\,353$$$.

Input: The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of dominoes.The next $$$n$$$ lines describe dominoes. Each line contains two characters which represent the left and the right cell. Character B means that the corresponding cell is black, character W means that the corresponding cell is white, and ? means that the cell is yet to be colored. 

Output: Print a single integer — the answer to the problem.

Note: In the first test case, there is only one domino, and we need the color of its right cell to be different from the color of its left cell. There is only one way to achieve this.In the second test case, there are only $$$2$$$ such colorings:BB WW and WB WB.

Sample Inputs:
1
?W

2
??
W?

4
BB
??
W?
??

Sample Outputs:
1

2

10

Solution (Python):
import sys
inpu = sys.stdin.readline
prin = sys.stdout.write
M = 998244353

def binom(n, m, mod):
    if m > n or m < 0:
        return 0
    fac = 1
    i = 1
    (a, b, c) = (1, 1, 1)
    while i <= n:
        fac = fac * i % mod
        if i == m:
            a = fac
        if i == n - m:
            b = fac
        if i == n:
            c = fac
        i += 1
    x = c * pow(a, -1, mod) * pow(b, -1, mod) % mod
    return x
n = int(inpu())
blank = 0
xw = 0
wx = 0
bb = 0
ww = 0
bx = 0
xb = 0
bw = 0
wb = 0
for i in range(n):
    s = input()
    if s[0] == '?':
        if s[1] == '?':
            blank += 1
        elif s[1] == 'W':
            xw += 1
        elif s[1] == 'B':
            xb += 1
    elif s[0] == 'W':
        if s[1] == '?':
            wx += 1
        elif s[1] == 'W':
            ww += 1
        elif s[1] == 'B':
            wb += 1
    elif s[0] == 'B':
        if s[1] == '?':
            bx += 1
        elif s[1] == 'W':
            bw += 1
        elif s[1] == 'B':
            bb += 1
diff = ww - bb
k = blank
m = wx + xw
n = bx + xb
tot = binom(m + n + 2 * k, m + k + diff, M)
if ww == bb == 0:
    ways = pow(2, blank, M)
    if bw == 0 and xw == 0 and (bx == 0):
        ways -= 1
    if wb == 0 and wx == 0 and (xb == 0):
        ways -= 1
    tot -= ways
print(tot)

Solution (Python):
import collections
import math
import itertools
import sys
import time
import random
mod = 998244353

def fast_input():
    return sys.stdin.readline().strip()
input = fast_input

def ints_input():
    return list((int(x) for x in input().split()))

def int_input():
    return int(input())

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        (g, y, x) = egcd(b % a, a)
        return (g, x - b // a * y, y)

def modinv(a, m):
    (g, x, y) = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def choose(n, k, p):
    if k == 0:
        return 1
    x = n
    for y in range(n - 1, n - k, -1):
        x = x * y % p
    d = 1
    for i in range(2, k + 1):
        d = d * i % p
    return x * modinv(d, p) % p

def solve():
    n = int_input()
    wb_poss = n > 1
    bw_poss = n > 1
    w = 0
    b = 0
    q = 0
    free = 0
    any_bad_poss = n > 1
    for _ in range(n):
        s = fast_input()
        if s[0] == 'B':
            b += 1
            wb_poss = False
        elif s[0] == 'W':
            w += 1
            bw_poss = False
        elif s[0] == '?':
            q += 1
        if s[1] == 'B':
            b += 1
            bw_poss = False
        elif s[1] == 'W':
            w += 1
            wb_poss = False
        elif s[1] == '?':
            q += 1
        if s == '??':
            free += 1
        elif s[0] == s[1]:
            any_bad_poss = False
    w_needed = n - w
    if w_needed > q or w_needed < 0:
        print(0)
        return
    if any_bad_poss:
        num_bad_poss = 1
        for i in range(free):
            num_bad_poss = num_bad_poss * 2 % mod
        num_bad_poss -= int(bw_poss) + int(wb_poss)
    else:
        num_bad_poss = 0
    print((choose(q, w_needed, mod) - num_bad_poss + mod) % mod)
if False:
    for _ in range(int_input()):
        solve()
else:
    solve()

Solution (Python):
import sys
inpu = sys.stdin.readline
prin = sys.stdout.write
M = 998244353

def binom(n, m, mod):
    if m > n or m < 0:
        return 0
    fac = 1
    i = 1
    (a, b, c) = (1, 1, 1)
    while i <= n:
        fac = fac * i % mod
        if i == m:
            a = fac
        if i == n - m:
            b = fac
        if i == n:
            c = fac
        i += 1
    x = c * pow(a, -1, mod) * pow(b, -1, mod) % mod
    return x
n = int(inpu())
blank = 0
xw = 0
wx = 0
bb = 0
ww = 0
bx = 0
xb = 0
bw = 0
wb = 0
for i in range(n):
    s = input()
    if s[0] == '?':
        if s[1] == '?':
            blank += 1
        elif s[1] == 'W':
            xw += 1
        elif s[1] == 'B':
            xb += 1
    elif s[0] == 'W':
        if s[1] == '?':
            wx += 1
        elif s[1] == 'W':
            ww += 1
        elif s[1] == 'B':
            wb += 1
    elif s[0] == 'B':
        if s[1] == '?':
            bx += 1
        elif s[1] == 'W':
            bw += 1
        elif s[1] == 'B':
            bb += 1
diff = ww - bb
k = blank
m = wx + xw
n = bx + xb
tot = binom(m + n + 2 * k, m + k + diff, M)
if ww == bb == 0:
    ways = pow(2, blank, M)
    if bw == 0 and xw == 0 and (bx == 0):
        ways -= 1
    if wb == 0 and wx == 0 and (xb == 0):
        ways -= 1
    tot -= ways
print(tot)