给定一种字符串压缩算法:对于连续的相同字母,会压缩成 该字母 + 出现次数 的形式,例如 aaabbcccc
会被压缩成 a3b2c4
,aaaaaaaaaa
会被压缩成 a10
。
字符集为英文小写字母,给定
DP 比价显然。考虑状态,设
考虑转移,显然对于某个状态的
这个东西显然是可以前缀和优化的,注意因为第二维的状态,所以要按照
然后这里我们要注意
这里还有两个易错点,一个是注意枚举状态的时候应为
另一个易错点是中间我们会需要求一次 log10
,如果一定要用换底做的话记得用 long double
,我最开始写的 #define log10(x) (int(log((double)x) / log(10.0)) + 1)
,然后这个东西因为精度问题会出现
xxxxxxxxxx
641
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27int N, MOD;
28ll ans(0);
29ll dp[3100][3100];
30ll sum[3100][3100];
31int pow10[5] = {1, 10, 100, 1000, 10000};
32
33int 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
50template < typename T >
51inline 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}
update-2022_11_30 初稿