Count The Blocks (Codeforces 1327E)
Tags: Math, combinatorics

You wrote down all integers from $$$0$$$ to $$$10^n - 1$$$, padding them with leading zeroes so their lengths are exactly $$$n$$$. For example, if $$$n = 3$$$ then you wrote out 000, 001, ..., 998, 999.A block in an integer $$$x$$$ is a consecutive segment of equal digits that cannot be extended to the left or to the right.For example, in the integer $$$00027734000$$$ there are three blocks of length $$$1$$$, one block of length $$$2$$$ and two blocks of length $$$3$$$.For all integers $$$i$$$ from $$$1$$$ to $$$n$$$ count the number of blocks of length $$$i$$$ among the written down integers.Since these integers may be too large, print them modulo $$$998244353$$$.

Input: The only line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Output: In the only line print $$$n$$$ integers. The $$$i$$$-th integer is equal to the number of blocks of length $$$i$$$.Since these integers may be too large, print them modulo $$$998244353$$$.


Sample Inputs:
1

2

Sample Outputs:
10

180 10

Solution (Python):
def solve():
    n = int(input())
    numbers = [10]
    power = 1
    mod = 998244353
    for i in range(2, n + 1):
        numbers.append(9 * (9 * i + 2) * power % mod)
        power = power * 10 % mod
    s = reversed(list(map(str, numbers)))
    print(' '.join(s))

def modpow(base, exponent, mod):
    res = 1
    power = base
    while exponent > 0:
        if exponent & 1:
            res = res * power % mod
        power = power * power % mod
        exponent //= 2
    return res
solve()

Solution (Python):
def f(n):
    if n == 1:
        return '10'
    if n == 2:
        return '180 10'
    s = 10 + 180
    p = 90
    g = [0] * (n - 2) + [180, 10]
    m = 998244353
    for i in range(n - 3, -1, -1):
        g[i] = ((s + p) * 10 - s) % m
        s = (s + g[i]) % m
        p = p * 10 % m
    return ' '.join(map(str, g))

def main():
    n = int(input())
    print(f(n))
main()

Solution (Python):
def read_int():
    return int(input().strip())

def read_ints():
    return list(map(int, input().strip().split(' ')))

def brute_solve():
    from collections import Counter
    from itertools import groupby
    n = 6
    counter = Counter()
    for i in range(10 ** n):
        for (k, vs) in groupby(f'{i:06}'):
            vs = list(vs)
            counter[len(vs)] += 1
    print(counter)

def solve():
    n = read_int()
    total = [0] * (n + 1)
    power_of_ten = 1
    mod = 998244353
    for k in range(n, 0, -1):
        if k == n:
            total[k] = 10
        elif k == n - 1:
            total[k] = 180
        else:
            power_of_ten = power_of_ten * 10 % mod
            total[k] = (99 + 81 * (n - k)) * power_of_ten % mod
    return ' '.join((str(t) for t in total[1:]))
if __name__ == '__main__':
    print(solve())