「CF1327E」Count The Blocks

发表于 分类于

Link

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

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

写下从 0…10n−1 的所有数，不足 n 位的用前导 0 补足。

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

n≤2×105，答案对 998244353 取模。

对于每个 i 分别考虑。

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

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

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

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

即 ansi=10×(n−i−1)×92×10n−i−2+10×2×9×10n−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;
}