Codeforces_forever Round #1 (Div3) Е

//решение
Предположим, что мы хотим посчитать количество блоков длины $$$len$$$. Разделим эти блоки на два типа:

блоки, которые находятся в начале и конце числа (например блоки $$$111$$$ и $$$0$$$ в числе $$$11173220$$$);
остальные блоки.
Для начала посчитаем количество блоков первого типа. Мы можем выбрать $$$2$$$ варианта расположения таких блоков (в начале и в конце числа). Теперь мы можем выбрать $$$10$$$ вариантов цифр для этого блока. Далее мы можем выбрать $$$9$$$ вариантов цифр для соседнего блока (если эти блоки будут состоять из одинаковых цифр, то длина блока, количество которого мы считаем будет больше $$$len$$$, а значит мы можем выбрать цифру соседнего блока только $$$9$$$ вариантами). Наконец, мы можем выбрать оставшиеся цифры $$$10^{n-len-1}$$$ способами.

Таким образом, суммарное количество блоков первого типа $$$2 \cdot 10 \cdot 9 \cdot 10^{n-len-1}$$$.

Теперь посчитаем количество блоков второго типа. Мы можем выбрать $$$n - len - 1$$$ вариантов расположения таких блоков (все варианты кроме начала и конца числа). Теперь мы можем выбрать $$$10$$$ вариантов цифр для этого блока. Далее мы можем выбрать $$$9^2$$$ вариантов цифр для соседнегих блоков ($$$9$$$ вариантов для блока слева и $$$9$$$ вариантов для блока справа). Наконец, мы можем выбрать оставшиеся цифры $$$10^{n-len-2}$$$ способами.

Таким образом, суммарное количество блоков второго типа $$$(n - len - 1) \cdot 10 \cdot 9^2 \cdot 10^{n-len-2}$$$.

На этом почти все. У нас есть один частный случай. Если $$$len = n$$$, то количество блоков будет равно $$$10$$$.
//реализация
#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int a, int b, int m = MOD) {
    return ((a % m) + (b % m)) % m;
}

int mul(int a, int b, int m = MOD) {
    return ((long long) (a % m) * (b % m)) % m;
}

int power(int b, int e, int m = MOD) {
    if (e == 0) return 1;
    int res = power(mul(b, b), e / 2);
    if (e % 2) res = mul(res, b);
    return res;
}

int solve(int x, int n) {
    int res = 0;
    if (x == n) res = add(res, 10);
    if (x + 1 <= n) res = mul(9, mul(2, power(10, n - x)));
    if (x + 2 <= n) res = add(res, mul(81, mul(n - x - 1, power(10, n - x - 1))));
    return res;
}

int main() {
    int n;
    cin >> n;
    for (int x = 1; x <= n; x++) {
        cout << solve(x, n) << " ";
    }
    cout << '\n';
}