题目大意

给定n（n < 2 * 10⁵），统计从 0 到 10ⁿ-1的所有数字（有前导零）中，统计不同长度的数字块的个数。

举个栗子： 9987654321 和 1999999999 两个数字中 len = 1 的数字块的个数为：9（前边那个数里有八个，后边有一个） len = 2 的数字块的个数为：1 len = 9 的数字块的个数为：1  

分析

先考虑最特殊的情况 n = len = x的时候，也就是n个数字全部相同，显然不管x取值为多少答案都是10

eg：x = 3 时，len = 3 的情况有： 000，111，222，333，444，555，666，777，888，999 

也就是说 （n=1，len=1）与（n=2.len=2）与（n=3，len=3）与（n=x，len=x）全部都是等价的
进而我们去想，还有没有其他的等价关系，比较容易想到的是（n=i，len=j）与（n=i-1，len=j-1）是等价的
举个栗子：（n=4，len=3）可以当作（n=3，len=2）中，每个块都再插入一个和这个块相同的数字对应关系如下：
331 –>> 3331
332 –>> 3332
333 –>> 3333
334 –>> 3334
335 –>> 3335
336 –>> 3336
337 –>> 3337
338 –>> 3338
339 –>> 3339
330 –>> 3330………… 列举一部分

到这里是不是就应该有这样一种奇妙想法（DP），如下图

不过，现在有一个很明显的问题，如上图中 （n=4，len=1）没办法从 （n=3，len=0）得到，毕竟 len = 0 不符合题意哎
题目有个隐藏的条件
还是拿上图的例子，从 0000 到 9999 一共出现多少个数字？
答案是 4 * 10⁴

那么就有：
(n=4，len=1) = 4 * 10^4 – (n=4, len=2) * 2 – (n=4, len=3) * 3 – (n=4,len=4)*4;

我们先定义一个sum[n] = dp[1] + dp[2] + …… + dp[n];
再定义一个tot[n] = sum[n-1] + sum[n-2] + …… + sum[1];
这时候就出现递归式：tot[n] = tot[n-1] + sum[n-1];

现在把上边那个图给稍作修改

现在就很明显了

（n=4，len=1）=  all[n] - (tot[n-1] + sum[n-1]) 

代码

#include <bits/stdc++.h> #define ll long long const ll mod = 998244353; const int maxn = 2e5 + 5; using namespace std;  ll dp[maxn] = {0, 10};  int main(){    ios::sync_with_stdio(false);     int n;   cin >> n; // 初始化    ll tot = dp[1];         ll sum = dp[1]; // sum = dp[1] + ... + dp[n]    ll all = 100; // 当前状态下一共有多少数字 ,从n=2开始  for(int i = 2; i <= n; i++){          dp[i] = ((all * i - tot - sum) % mod + mod) % mod; //（（x - y）% mod + mod） % mod  是取模的一个技巧 避免答案出现负数           sum = (sum + dp[i]) % mod; // 更新 sum           tot = (tot + sum) % mod; // 更新 tot           all = (all * 10) % mod; // all = 10^i;  } for(int i = n; i >= 1; i--) cout << dp[i] << " "; //输出的时候要倒这输 dp[1]里边存的是 （n=n，len=n）的答案；  return 0; }

第一次写博客，大佬轻喷！