AtCoder Beginner Contest 249 E - RLE
2022-05-11 03:44 作者:Asunataisiki | 我要投稿
题意：求满足原长度为n，且经过转换规则之后长度严格小于n的原字符串有多少种
其中，转换规则为，将连续的字母表示为原字母+字母个数，例如aaa转化为a3
思路：一眼dp，首先考虑暴力求解，表示原串长度为
且转换长度后为
的数量，那么考虑在当前长度
的情况下，在后面接一个长度为
的字符串（每个字母均相同），可以表示为
，其中
表示经过转换规则之后的长度，乘25的原因是，需要与原串最后一个字母不同，共有25中情况，可以发现这是个
的复杂度，需要优化
这里面首先能想到的就是优化
发现可以分区间了，所以
用前缀和来优化掉每一个求和
注意处理边界，但是不懂为什么要在前缀和相减的时候加上p，不加就wa，加了就过了
#include<bits/stdc++.h>
#define endl '\n'
#define fr first
#define se second
#define mem(x, y) memset(x, y, sizeof x)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
//右左上下
const int N = 3005;
LL f[N][N], sum[N][N];
///f表示长度为i的字符串，用计数法表示后长度为j的数量
///s表示长度为2 ~ i的字符串，用计数法表示后长度为j的数量
void solve()
{
int n, p;
cin >> n >> p;
//f[0][0] = 1;
for(int i = 1; i <= n; i++) {
int k = 1 + to_string(i).size();
if(k < n) {
f[i][k] += 26; f[i][k] %= p;
}
///题目要求压缩后的长度j < n，所以这里不取等
for(int j = 2; j <= 2 * i && j < n; j++) {
f[i][j] += 25 * (p + sum[max(0, i - 1)][max(0, j - 2)] - sum[max(0, i - 10)][max(0, j - 2)]) % p;
f[i][j] += 25 * (p + sum[max(0, i - 10)][max(0, j - 3)] - sum[max(0, i - 100)][max(0, j - 3)]) % p;
f[i][j] += 25 * (p + sum[max(0, i - 100)][max(0, j - 4)] - sum[max(0, i - 1000)][max(0, j - 4)]) % p;
f[i][j] += 25 * (p + sum[max(0, i - 1000)][max(0, j - 5)] - sum[max(0, i - 10000)][max(0, j - 5)]) % p;
f[i][j] %= p;
sum[i][j] = sum[i - 1][j] + f[i][j];
sum[i][j] %= p;
}
}
LL ans = 0;
for(int i = 1; i < n; i++) {
ans += f[n][i];
ans %= p;
}
cout << ans << endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
// 315397365