[ABC249E] RLE Solution
目录更好的阅读体验戳此进入
题面
给定一种字符串压缩算法:对于连续的相同字母,会压缩成 该字母 + 出现次数 的形式,例如 aaabbcccc
会被压缩成 a3b2c4
,aaaaaaaaaa
会被压缩成 a10
。
字符集为英文小写字母,给定 $ n, p $,求对于所有长度为 $ n $ 的字符串,有多少满足压缩后的字符串长度严格小于原字符串。对 $ p $ 取模。保证 $ p $ 为质数。
Solution
DP 比价显然。考虑状态,设 $ dp(i, j) $ 表示考虑前 $ i $ 个字符,压缩后长度为 $ j $ 的方案数。
考虑转移,显然对于某个状态的 $ i $ 可以从前面所有长度小于它的 $ k $ 转移而来,并且钦定 $ [k, i] $ 是相同的,且与 $ k - 1 $ 不同。所以转移的时候还需要考虑那一段压缩后的长度,也就是 $ \log_{10} $。显然有:
\[dp(i, j) = \sum_{k = 1}^{i}dp(k - 1, j - \log_{10}^{i - k + 1} - 1) \times 25 \]这个东西显然是可以前缀和优化的,注意因为第二维的状态,所以要按照 $ \log_{10}^{i - k + 1} $ 做,最后的复杂度 $ O(n^3) \longrightarrow O(n^2 \log n) $,且 $ \log $ 是以 $ 10 $ 为底的,可以通过。
然后这里我们要注意 $ dp(1, x) $ 的时候这个东西是可以取到 $ 26 $ 个字符的,而不是 $ 25 $,所以这里有个小 trick,因为是模意义下的且模数为质数,所以可以直接求个逆元然后令 $ dp(0, 0) = \dfrac{26}{25} \bmod{p} $,这样转移的时候就可以直接按照柿子无脑写了,当然在具体实现的时候,还是推荐直接初始化 $ dp(i, \log_{10}^i) $,这样虽然会使代码略显冗长,但是也会更直观,好调。
这里还有两个易错点,一个是注意枚举状态的时候应为 $ j \le n $ 而非 $ j \lt i $,因为 $ j \ge i $ 的虽然在当前是不合法的,但是转移到后面之后会因被压缩而变得合法,所以也需要记录。
另一个易错点是中间我们会需要求一次 $ \log $,这个东西因为数据范围较小,建议直接枚举手写,不过如果非要像我一样用浮点运算,建议直接用库里的 log10
,如果一定要用换底做的话记得用 long double
,我最开始写的 #define log10(x) (int(log((double)x) / log(10.0)) + 1)
,然后这个东西因为精度问题会出现 $ \operatorname{log10}(1000) = 3 $,找了好久才发现是这个的问题。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define log10_(x) (int(logl((ld)x) / logl((ld)10.0)) + 1)
template < typename T = int >
inline T read(void);
int N, MOD;
ll ans(0);
ll dp[3100][3100];
ll sum[3100][3100];
int pow10[5] = {1, 10, 100, 1000, 10000};
int main(){
N = read(), MOD = read();
for(int i = 1; i <= N; ++i){
dp[i][(int)log10(i) + 2] = 26;
for(int j = 1; j <= N; ++j){
for(int len = 0; len <= 3; ++len)
if(i >= pow10[len] && j - 2 - len > 0)
(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;
sum[i][j] = (sum[i - 1][j] + dp[i][j]) % MOD;
}
}
for(int i = 1; i < N; ++i)(ans += dp[N][i]) %= MOD;
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2022_11_30 初稿
标签:10,log,RLE,题解,MOD,int,define,dp,ABC249E From: https://www.cnblogs.com/tsawke/p/16945742.html