[ABC249E] RLE Solution

更好的阅读体验戳此进入

题面

给定一种字符串压缩算法：对于连续的相同字母，会压缩成 该字母 + 出现次数 的形式，例如 aaabbcccc 会被压缩成 a3b2c4，aaaaaaaaaa 会被压缩成 a10。

字符集为英文小写字母，给定 $n,p$$n, p$，求对于所有长度为 $n$$n$ 的字符串，有多少满足压缩后的字符串长度严格小于原字符串。对 $p$$p$ 取模。保证 $p$$p$ 为质数。

Solution

DP 比价显然。考虑状态，设 $dp(i,j)$$dp(i, j)$ 表示考虑前 $i$$i$ 个字符，压缩后长度为 $j$$j$ 的方案数。

考虑转移，显然对于某个状态的 $i$$i$ 可以从前面所有长度小于它的 $k$$k$ 转移而来，并且钦定 $[k,i]$$[k, i]$ 是相同的，且与 $k-1$$k - 1$ 不同。所以转移的时候还需要考虑那一段压缩后的长度，也就是 ${\log }_{10}$$\log_{10}$。显然有：

这个东西显然是可以前缀和优化的，注意因为第二维的状态，所以要按照 ${\log }_{10}^{i-k+1}$$\log_{10}^{i - k + 1}$ 做，最后的复杂度 $O(n^3)⟶O(n^2\log n)$$O(n^3) \longrightarrow O(n^2 \log n)$，且 $\log$$\log$ 是以 $10$$10$ 为底的，可以通过。

然后这里我们要注意 $dp(1,x)$$dp(1, x)$ 的时候这个东西是可以取到 $26$$26$ 个字符的，而不是 $25$$25$，所以这里有个小 trick，因为是模意义下的且模数为质数，所以可以直接求个逆元然后令 $dp(0,0)={\displaystyle \frac{26}{25}}modp$$dp(0, 0) = \dfrac{26}{25} \bmod{p}$，这样转移的时候就可以直接按照柿子无脑写了，当然在具体实现的时候，还是推荐直接初始化 $dp(i,{\log }_{10}^i)$$dp(i, \log_{10}^i)$，这样虽然会使代码略显冗长，但是也会更直观，好调。

这里还有两个易错点，一个是注意枚举状态的时候应为 $j\le n$$j \le n$ 而非 $j<i$$j \lt i$，因为 $j\ge i$$j \ge i$ 的虽然在当前是不合法的，但是转移到后面之后会因被压缩而变得合法，所以也需要记录。

另一个易错点是中间我们会需要求一次 $\log$$\log$，这个东西因为数据范围较小，建议直接枚举手写，不过如果非要像我一样用浮点运算，建议直接用库里的 log10，如果一定要用换底做的话记得用 long double，我最开始写的 #define log10(x) (int(log((double)x) / log(10.0)) + 1)，然后这个东西因为精度问题会出现 $\log 10(1000)=3$$\operatorname{log10}(1000) = 3$，找了好久才发现是这个的问题。

Code

xxxxxxxxxx
64
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define log10_(x) (int(logl((ld)x) / logl((ld)10.0)) + 1)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, MOD;
28
ll ans(0);
29
ll dp[3100][3100];
30
ll sum[3100][3100];
31
int pow10[5] = {1, 10, 100, 1000, 10000};
32

33
int main(){
34
    N = read(), MOD = read();
35
    for(int i = 1; i <= N; ++i){
36
        dp[i][(int)log10(i) + 2] = 26;
37
        for(int j = 1; j <= N; ++j){
38
            for(int len = 0; len <= 3; ++len)
39
                if(i >= pow10[len] && j - 2 - len > 0)
40
                    (dp[i][j] += ((sum[i - pow10[len]][j - 2 - len] - sum[max(i - pow10[len + 1], 0)][j - 2 - len] + MOD) % MOD * 25ll % MOD)) %= MOD;
41
            sum[i][j] = (sum[i - 1][j] + dp[i][j]) % MOD;
42
        }
43
    }
44
    for(int i = 1; i < N; ++i)(ans += dp[N][i]) %= MOD;
45
    printf("%lld\n", ans);
46
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
47
    return 0;
48
}
49

50
template < typename T >
51
inline T read(void){
52
    T ret(0);
53
    int flag(1);
54
    char c = getchar();
55
    while(c != '-' && !isdigit(c))c = getchar();
56
    if(c == '-')flag = -1, c = getchar();
57
    while(isdigit(c)){
58
        ret *= 10;
59
        ret += int(c - '0');
60
        c = getchar();
61
    }
62
    ret *= flag;
63
    return ret;
64
}

UPD

update-2022_11_30 初稿