Turtle Magic: Royal Turtle Shell Pattern (Codeforces 1933G)
Tags: Math, bitmasks

Turtle Alice is currently designing a fortune cookie box, and she would like to incorporate the theory of LuoShu into it.The box can be seen as an $$$n \times m$$$ grid ($$$n, m \ge 5$$$), where the rows are numbered $$$1, 2, \dots, n$$$ and columns are numbered $$$1, 2, \dots, m$$$. Each cell can either be empty or have a single fortune cookie of one of the following shapes: circle or square. The cell at the intersection of the $$$a$$$-th row and the $$$b$$$-th column is denoted as $$$(a, b)$$$.Initially, the entire grid is empty. Then, Alice performs $$$q$$$ operations on the fortune cookie box. The $$$i$$$-th operation ($$$1 \le i \le q$$$) is as follows: specify a currently empty cell $$$(r_i,c_i)$$$ and a shape (circle or square), then put a fortune cookie of the specified shape on cell $$$(r_i,c_i)$$$. Note that after the $$$i$$$-th operation, the cell $$$(r_i,c_i)$$$ is no longer empty.Before all operations and after each of the $$$q$$$ operations, Alice wonders what the number of ways to place fortune cookies in all remaining empty cells is, such that the following condition is satisfied:No three consecutive cells (in horizontal, vertical, and both diagonal directions) contain cookies of the same shape. Formally:  There does not exist any $$$(i,j)$$$ satisfying $$$1 \le i \le n, 1 \le j \le m-2$$$, such that there are cookies of the same shape in cells $$$(i,j), (i,j+1), (i,j+2)$$$.  There does not exist any $$$(i,j)$$$ satisfying $$$1 \le i \le n-2, 1 \le j \le m$$$, such that there are cookies of the same shape in cells $$$(i,j), (i+1,j), (i+2,j)$$$.  There does not exist any $$$(i,j)$$$ satisfying $$$1 \le i \le n-2, 1 \le j \le m-2$$$, such that there are cookies of the same shape in cells $$$(i,j), (i+1,j+1), (i+2,j+2)$$$.  There does not exist any $$$(i,j)$$$ satisfying $$$1 \le i \le n-2, 1 \le j \le m-2$$$, such that there are cookies of the same shape in cells $$$(i,j+2), (i+1,j+1), (i+2,j)$$$. You should output all answers modulo $$$998\,244\,353$$$. Also note that it is possible that after some operations, the condition is already not satisfied with the already placed candies, in this case you should output $$$0$$$.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$5 \le n, m \le 10^9, 0 \le q \le \min(n \times m, 10^5)$$$).The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$r_i$$$, $$$c_i$$$ and a single string $$$\text{shape}_i$$$ ($$$1 \le r_i \le n, 1 \le c_i \le m$$$, $$$\text{shape}_i=$$$ "circle" or "square"), representing the operations. It is guaranteed that the cell on the $$$r_i$$$-th row and the $$$c_i$$$-th column is initially empty. That means, each $$$(r_i,c_i)$$$ will appear at most once in the updates.The sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output $$$q+1$$$ lines. The first line of each test case should contain the answer before any operations. The $$$i$$$-th line ($$$2 \le i \le q+1$$$) should contain the answer after the first $$$i-1$$$ operations. All answers should be taken modulo $$$998\,244\,353$$$.

Note: In the second sample, after placing a circle-shaped fortune cookie to cells $$$(1,1)$$$, $$$(1,2)$$$ and $$$(1,3)$$$, the condition is already not satisfied. Therefore, you should output $$$0$$$.

Sample Inputs:
2
6 7 4
3 3 circle
3 6 square
5 3 circle
5 4 square
5 5 3
1 1 circle
1 2 circle
1 3 circle

Sample Outputs:
8
4
3
1
0
8
4
1
0

Solution (Python):
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
import bisect
import math
A = [[]] * 8
A[0] = [[0, 0, 1, 1], [1, 1, 0, 0]]
A[1] = [[0, 1, 1, 0], [1, 0, 0, 1]]
A[2] = [[1, 1, 0, 0], [0, 0, 1, 1]]
A[3] = [[1, 0, 0, 1], [0, 1, 1, 0]]
A[4] = [[0, 1], [0, 1], [1, 0], [1, 0]]
A[5] = [[0, 1], [1, 0], [1, 0], [0, 1]]
A[6] = [[1, 0], [1, 0], [0, 1], [0, 1]]
A[7] = [[1, 0], [0, 1], [0, 1], [1, 0]]

def solve():
    (n, m, q) = map(int, stdin.readline().split())
    print(8)
    res = 8
    left = [True] * 8

    def check(x, y, type):
        nonlocal res
        for i in range(8):
            if left[i]:
                (r, c) = (len(A[i]), len(A[i][0]))
                if A[i][x % r][y % c] != type:
                    left[i] = False
    for _ in range(q):
        (x, y, type) = stdin.readline().split()
        (x, y) = (int(x) - 1, int(y) - 1)
        type = 1 if type[0] == 'c' else 0
        check(x, y, type)
        print(sum([x for x in left]))
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
import bisect
import math
A = [[]] * 8
A[0] = [[0, 0, 1, 1], [1, 1, 0, 0]]
A[1] = [[0, 1, 1, 0], [1, 0, 0, 1]]
A[2] = [[1, 1, 0, 0], [0, 0, 1, 1]]
A[3] = [[1, 0, 0, 1], [0, 1, 1, 0]]
A[4] = [[0, 1], [0, 1], [1, 0], [1, 0]]
A[5] = [[0, 1], [1, 0], [1, 0], [0, 1]]
A[6] = [[1, 0], [1, 0], [0, 1], [0, 1]]
A[7] = [[1, 0], [0, 1], [0, 1], [1, 0]]

def solve():
    (n, m, q) = map(int, stdin.readline().split())
    print(8)
    left = [True] * 8

    def check(x, y, type):
        for i in range(8):
            if left[i]:
                (r, c) = (len(A[i]), len(A[i][0]))
                if A[i][x % r][y % c] != type:
                    left[i] = False
    for _ in range(q):
        (x, y, type) = stdin.readline().split()
        (x, y) = (int(x) - 1, int(y) - 1)
        type = 1 if type[0] == 'c' else 0
        check(x, y, type)
        print(sum([x for x in left]))
T = int(input())
for _ in range(T):
    solve()

Solution (Python):
from collections import *
d = defaultdict(set)
arr = ['0011110000111100', '0110100101101001', '0101101010100101', '0101010110101010']
for (i, item) in enumerate(arr):
    for j in range(16):
        d[j % 4, j // 4, int(item[j])].add(i)
for (i, item) in enumerate(arr):
    for j in range(16):
        d[j % 4, j // 4, int(item[j]) ^ 1].add(i + 4)
for _ in range(int(input())):
    (m, n, q) = map(int, input().split())
    print(8)
    tran = {'circle': 0, 'square': 1}
    store = set()
    for _ in range(q):
        (i, j, k) = input().split()
        (i, j, k) = (int(i) % 4, int(j) % 4, tran[k])
        store.update(d[i, j, k])
        print(8 - len(store))