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

本文主要是介绍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;
}

这篇关于Codeforces1327 E. Count The Blocks（DP，容斥）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---