「CF1327E」Count The Blocks

发表于 分类于

$Link$

定义一个数中，连续 $k$ 个数相等，为一个长度为 $k$ 的块。

要求块外两端的数字不同于块内数字。

写下从 $0\dots 10^n-1$ 的所有数，不足 $n$ 位的用前导 $0$ 补足。

对于每一个 $i=1\dots n$ 求这些数中有多少长度为 $i$ 的块。

$n\le 2\times 10^5$，答案对 $998244353$ 取模。

对于每个 $i$ 分别考虑。

块内数字有 $10$ 种，块两端数字有 $9$ 种，剩余 $n-i-2$ 个数字均为 $10$ 种。

块的起始位置有 $n-i+1$ 种。

注意到如果块的起始位置为 $1$，或块的结束位置为 $n$，两端数字要求变为一端。

由乘法原理可知，设长度为 $i$ 的块有 $ans_i$ 个，则 $ans_i=$ 块内数字 $\times$ 起始位置 $\times$ 两（一）端数字 $\times$ 剩余数字。

即 $ans_i=10\times (n-i-1)\times 9^2\times 10^{n-i-2}+10\times 2\times 9\times 10^{n-i+1}$。

记得取模。

时间复杂度 $O(n)$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define ll long long
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const ll mod = 998244353;
const int N = 2e5;

int n;
ll w[N + 1];

int main()
{
    n = read();
    w[0] = 1;
    for (int i = 1; i <= n; i++)
        w[i] = (w[i - 1] * 10) % mod;

    for (int i = 1; i <= n; i++) {
        if (i == n) {
            printf("10\n");
            continue;
        }
        ll ans = 0;
        ans = (ans + (180 * w[n - i - 1]) % mod) % mod;
        if (n - i >= 2)
            ans = (ans + (810 * (n - i - 1) % mod * w[n - i - 2]) % mod) % mod;
        printf("%lld ", ans);
    }

    return 0;
}