AtCoder Beginner Contest 249 E - RLE
2022-05-11 03:44 作者:Asunataisiki | 我要投稿
題意：求滿足原長度為n，且經(jīng)過轉(zhuǎn)換規(guī)則之后長度嚴(yán)格小于n的原字符串有多少種
其中，轉(zhuǎn)換規(guī)則為，將連續(xù)的字母表示為原字母+字母個數(shù)，例如aaa轉(zhuǎn)化為a3
思路：一眼dp，首先考慮暴力求解，表示原串長度為?
且轉(zhuǎn)換長度后為?
的數(shù)量，那么考慮在當(dāng)前長度
的情況下，在后面接一個長度為
的字符串（每個字母均相同），可以表示為
，其中
表示經(jīng)過轉(zhuǎn)換規(guī)則之后的長度，乘25的原因是，需要與原串最后一個字母不同，共有25中情況，可以發(fā)現(xiàn)這是個
的復(fù)雜度，需要優(yōu)化
這里面首先能想到的就是優(yōu)化?
發(fā)現(xiàn)可以分區(qū)間了，所以
用前綴和來優(yōu)化掉每一個求和
注意處理邊界，但是不懂為什么要在前綴和相減的時候加上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的字符串，用計數(shù)法表示后長度為j的數(shù)量
///s表示長度為2 ~ i的字符串，用計數(shù)法表示后長度為j的數(shù)量
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標(biāo)簽：
