E. Count The Blocks

Link: E. Count The Blocks

Description

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$.

Examples
input
1
output
10
input
2
output
180 10

Problem solving

这道题的意思就是给你一个数$n$，让你往这n位上面随意放置$0-9$这$10$个数字。问你所有摆放情况中，每种长度个相邻且相等的子串的个数。（$123000$中有$3$个长度为$1$的($1,2,3$)，$1$个长度为$3$的($000$)）
排列组合的问题，我们分情况考虑一下。假设现在求得是长度为$i$的子串个数

1. 这个串在最左边或者最右边。此时这个长度为$i$的子串有$10$种情况（$0-9$），与这个子串相邻的下（上）一位不能和它相等，若相等长度就是$i+1$了。所以只有$9$种情况。剩下的$n-i-1$位这$10$个数可以随便填。所以这种情况下的长度为$i$的字串个数$=10*2*9*10^{n-i-1}$，乘$2$是因为可以在左右两边。
2. 这个串处于中间。此时这个长度为$i$的子串也是有$10$种情况（$0-9$），与它相邻的两位，都只有$9$种情况。剩下的$n-i-2$位可以随便填。在长度为$n$的串中长度为$i$的子串个数为$n-i+1$，但是左右两边的不是这种情况讨论的，所以还剩下$n-i-1$种。所以这种情况下的长度为$i$的子串个数$=10*9*9*10^{n-i-2}*(n-i+1)$。

将两种情况得到的答案加起来即可。长度为$n$的情况比较特殊我们直接输出就好了。

可能是我高中数学或者概率论没有学好吧，这种题（一言难尽）

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
const int maxn = 2e5 + 10;
const int mod = 998244353;
ll ten[maxn];
int main() {
    ios::sync_with_stdio(0);
    ten[0]=1;
    for(int i=1;i<maxn;i++) ten[i]=ten[i-1]*10%mod;
    ll n;
    cin>>n;
    for(int i=1;i<n;i++){
        ll ans=(2ll*9ll*ten[n-i]%mod+9ll*9ll*ten[n-i-1]*(n-i-1)%mod)%mod;
        cout<<ans<<" ";
    }
    cout<<10<<endl;
    return 0;
}