Codeforces1327 E. Count The Blocks（DP，容斥）

You wrote down all integers from 0 to 10𝑛−1, padding them with leading zeroes so their lengths are exactly 𝑛. For example, if 𝑛=3 then you wrote out 000, 001, …, 998, 999.

A block in an integer 𝑥 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 𝑖 from 1 to 𝑛 count the number of blocks of length 𝑖 among the written down integers.

Since these integers may be too large, print them modulo 998244353.

Input The only line contains one integer 𝑛 (1≤𝑛≤2⋅105).

Output In the only line print 𝑛 integers. The 𝑖-th integer is equal to the number of blocks of length 𝑖.

Since these integers may be too large, print them modulo 998244353.

Examples inputCopy 1 outputCopy 10 inputCopy 2 outputCopy 180 10

题意： 输入一个n，代表n位数，范围为0000…——9999… 相同最大连续数字代表一个块，大小为其长度。 求这个n位数的所有数字的所有长度块的数目。

思路： 定义$dp[i][j]$代表长度为位数为$i$，长度为$j$块的个数。 则有$dp[i][j]=dp[i-1][j-1]$，因为很明显可以添加的这个位数到$i-1$位的长度为$j-1$块中。 初始条件$dp[1][1]=10$，那么关键就是计算$dp[i][1]$，这部分可以容斥求。 假设是$i$位数，那么总的数字个数为$i\ast 10^i$，所有非法的数字个数为$dp[i][2]\ast 2+dp[i][3]\ast 3+dp[i][4]\ast 4...$ 那么$dp[i][1]=i\ast 10^i-\sum dp[i][j]\ast j$。 这个前缀和可以递推维护出来，也就是$\sum dp[i][j]\ast j=\sum dp[i-1][j-1]\ast (j-1)+\sum dp[i-1][j-1]$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include <set> #include <map> #include <queue> using namespace std; typedef long long ll; const int maxn = 2e5 + 7; const int mod = 998244353; ll a[maxn]; int main() { int n;scanf("%d",&n); a[1] = 10; ll now = 0; ll sum = 10; ll p = 10; for(int i = 2;i <= n;i++) { p = p * 10 % mod; now += sum; now += a[i - 1]; now %= mod; a[i] = ((p * i % mod - now) % mod + mod) % mod; sum += a[i]; sum %= mod; now %= mod; sum %= mod; } for(int i = n;i >= 1;i--) { printf("%lld ",a[i]); } return 0; }