Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）

E - RLE

Time Limit: 3 sec / Memory Limit: 1024 MB

Score : $500$ points

### Problem Statement

Consider the following procedure of, given a string $X$ consisting of lowercase English alphabets, obtaining a new string:

• Split the string $X$ off at the positions where two different characters are adjacent to each other.
• For each string $Y$ that has been split off, replace $Y$ with a string consisting of the character which $Y$ consists of, followed by the length of $Y$.
• Concatenate the replaced strings without changing the order.

For example, aaabbcccc is divided into aaa,bb,cccc, which are replaced by a3,b2,c4, respectively, which in turn are concatenated without changing the order, resulting in a3b2c4.If the given string is aaaaaaaaaa , the new string is a10 .

Find the number, modulo $P$, of strings $S$ of lengths $N$ consisting of lowercase English alphabets, such that the length of $T$ is smaller than that of $S$, where $T$ is the string obtained by the procedure above against the string $S$.

### Constraints

• $1 \le N \le 3000$
• $10^8 \le P \le 10^9$
• $N$ and $P$ are integers.
• $P$ is a prime.

### Input

Input is given from Standard Input in the following format:

$N$ $P$

3 998244353

### Sample Output 1

26

Those strings of which the $1$-st, $2$-nd, and $3$-rd characters are all the same satisfy the condition.

For example, aaa becomes a3, which satisfies the condition, while abc becomes a1b1c1, which does not.

2 998244353

### Sample Output 2

0

Note that if a string is transformed into another string of the same length, such as aa that becomes a2, it does not satisfy the condition.

5 998244353

### Sample Output 3

2626

Strings like aaabb and aaaaa satisfy the condition.

3000 924844033

### Sample Output 4

607425699

Find the number of strings satisfying the condition modulo $P$.

### 我的笔记

#### 核心思想：动态规划

$dp[i][j]:=$ 原长为 $i$，转化后长为 $j$ 的字符串种数。

f(x)=\left\{ \begin{aligned} &2 \quad 1 \leq x<10\\ &3 \quad 10 \leq x<100\\ &4 \quad 100 \leq x<1000\\ &5 \quad 1000 \leq x<10000 \end{aligned} \right .

for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
for (int k = 1; k <= N - i; k++)
if (j + length(k) <= N)
{dp[i + k][j + length(k)] += 25 * dp[i][j] % P; dp[i + k][j + length(k)] %= P;}

$O(N^3)$，超时无疑

### 代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3010;
long long dp[MAXN][MAXN * 2], presum[MAXN][MAXN * 2];

inline int length(int x)
{
if (x >= 1000)
return 5;
else if (x >= 100)
return 4;
else if (x >= 10)
return 3;
else
return 2;
}

int main()
{
int N, P;
cin >> N >> P;
for (int i = 1; i <= N; i++)
dp[i][length(i)] = 26;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
for (int k = 1, len = 2; k < i && len < j; k *= 10, len++)
{
int l = max(0, i - k * 10), r = i - k;
dp[i][j] += 25 * (presum[r][j - len] - presum[l][j - len] + P) % P;
}
presum[i][j] = (presum[i - 1][j] + dp[i][j]) % P;
}
}
long long ans = 0;
for (int i = 1; i < N; i++)
{
ans += dp[N][i];
ans %= P;
}
cout << ans << endl;
return 0;
}