Tokitsukaze and Meeting (Codeforces 1678D)
Tags: Implement, dp

Tokitsukaze is arranging a meeting. There are $$$n$$$ rows and $$$m$$$ columns of seats in the meeting hall.There are exactly $$$n \cdot m$$$ students attending the meeting, including several naughty students and several serious students. The students are numerated from $$$1$$$ to $$$n\cdot m$$$. The students will enter the meeting hall in order. When the $$$i$$$-th student enters the meeting hall, he will sit in the $$$1$$$-st column of the $$$1$$$-st row, and the students who are already seated will move back one seat. Specifically, the student sitting in the $$$j$$$-th ($$$1\leq j \leq m-1$$$) column of the $$$i$$$-th row will move to the $$$(j+1)$$$-th column of the $$$i$$$-th row, and the student sitting in $$$m$$$-th column of the $$$i$$$-th row will move to the $$$1$$$-st column of the $$$(i+1)$$$-th row.For example, there is a meeting hall with $$$2$$$ rows and $$$2$$$ columns of seats shown as below:  There will be $$$4$$$ students entering the meeting hall in order, represented as a binary string "1100", of which '0' represents naughty students and '1' represents serious students. The changes of seats in the meeting hall are as follows:  Denote a row or a column good if and only if there is at least one serious student in this row or column. Please predict the number of good rows and columns just after the $$$i$$$-th student enters the meeting hall, for all $$$i$$$.

Input: The first contains a single positive integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.For each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n,m \leq 10^6$$$; $$$1 \leq n \cdot m \leq 10^6$$$), denoting there are $$$n$$$ rows and $$$m$$$ columns of seats in the meeting hall.The second line contains a binary string $$$s$$$ of length $$$n \cdot m$$$, consisting only of zeros and ones. If $$$s_i$$$ equal to '0' represents the $$$i$$$-th student is a naughty student, and $$$s_i$$$ equal to '1' represents the $$$i$$$-th student is a serious student.It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, print a single line with $$$n \cdot m$$$ integers — the number of good rows and columns just after the $$$i$$$-th student enters the meeting hall.

Note: The first test case is shown in the statement.After the $$$1$$$-st student enters the meeting hall, there are $$$2$$$ good rows and columns: the $$$1$$$-st row and the $$$1$$$-st column.After the $$$2$$$-nd student enters the meeting hall, there are $$$3$$$ good rows and columns: the $$$1$$$-st row, the $$$1$$$-st column and the $$$2$$$-nd column.After the $$$3$$$-rd student enters the meeting hall, the $$$4$$$ rows and columns are all good.After the $$$4$$$-th student enters the meeting hall, there are $$$3$$$ good rows and columns: the $$$2$$$-nd row, the $$$1$$$-st column and the $$$2$$$-nd column.

Sample Inputs:
3
2 2
1100
4 2
11001101
2 4
11001101

Sample Outputs:
2 3 4 3
2 3 4 3 5 4 6 5
2 3 3 3 4 4 4 5

Solution (Python):
from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
from collections import deque, Counter, OrderedDict, defaultdict
import heapq
from bisect import bisect_left, bisect_right
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return int(input())

def inps():
    return input().strip()

def lint():
    return list(map(int, input().split()))

def insr():
    s = input().strip()
    return list(s[:len(s)])

def invr():
    return map(int, input().split())
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def gcd(a, b):
    while b:
        a %= b
        tmp = a
        a = b
        b = tmp
    return a
t = 1
t = I()
for _ in range(t):
    (n, m) = lint()
    s = list(map(int, input().strip()))
    dp = [[0] * m for i in range(2)]
    res = [0] * (n * m)
    cnt = 0
    for i in range(n * m):
        if i // m % 2 == 0:
            if dp[1][i % m] == 0:
                cnt += s[i]
                dp[0][i % m] = s[i]
            else:
                dp[0][i % m] = dp[1][i % m]
        elif dp[0][i % m] == 0:
            cnt += s[i]
            dp[1][i % m] = s[i]
        else:
            dp[1][i % m] = dp[0][i % m]
        res[i] = cnt
    res2 = [0] * m
    last = -1000000000.0
    for i in range(n * m):
        if s[i] == 1:
            last = i
        if i - last < m:
            res2[i % m] += 1
        res[i] += res2[i % m]
    print(*res)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10 ** 5)

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
t = int(input())
for i in range(t):
    (n, m) = map(int, input().split())
    s = input()
    b = [0]
    for j in s:
        b.append(int(j))
    sm = 0
    curr = [0 for i in range(m)]
    cnt = [0 for i in range(m * n + 1)]
    for x in range(1, m + 1):
        k = x % m
        sm -= curr[k]
        if b[x] == 1:
            curr[k] = 1
        sm += curr[k]
        cnt[x] = sm
    tot = n * m
    for x in range(m + 1, tot + 1):
        k = x % m
        sm -= curr[k]
        if b[x] == 1:
            curr[k] = 1
        sm += curr[k]
        cnt[x] = sm
    curr = [0 for i in range(m)]
    tot = 1
    sm = 0
    for x in range(1, m + 1):
        k = x % m
        sm += b[x]
        if sm == 0:
            curr[k] += 1
        cnt[x] += tot - curr[k]
    q = n * m
    for x in range(m + 1, q + 1):
        k = x % m
        if k == 1 or m == 1:
            tot += 1
        sm += b[x] - b[x - m]
        if sm == 0:
            curr[k] += 1
        cnt[x] += tot - curr[k]
    print(*cnt[1:])

Solution (Python):
import copy
import gc
from array import array
from fractions import Fraction
import heapq
import math
import operator
import os, sys
import profile
import cProfile
import random
import re
import string
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
from functools import reduce
from io import IOBase, BytesIO
from itertools import count, groupby, accumulate, permutations, combinations_with_replacement
from math import gcd
from operator import xor, add
from typing import List
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_int_tuple():
    return tuple(map(int, input().split()))

def read_int():
    return int(input())

def solve(n, m, s: str):
    res = [0] * (n * m)
    (cols, col_cnt) = ([False] * m, 0)
    (row_cnts, pre) = ([0] * (n * m), -m)
    for (i, ch) in enumerate(s):
        j = i % m
        if ch == '1':
            pre = i
            if cols[j] == False:
                col_cnt += 1
                cols[j] = True
        row_cnts[i] = row_cnts[i - m]
        if i - pre < m:
            row_cnts[i] += 1
        res[i] = col_cnt + row_cnts[i]
    return res

def main():
    for t in range(read_int()):
        (n, m) = read_int_tuple()
        s = input()
        print(*solve(n, m, s))
if __name__ == '__main__':
    main()