思路
定义 \(dp_{i,j}\) 表示在前 \(i\) 位原字符串，压缩为 \(j\) 位的方案数。
不难得出状态转移方程：
\[ dp_{i,j} = \sum_{k = 1}^{i}(25 \times dp_{k,j - \lfloor \log_{10}k \rfloor - 1}) \]这样搞是 \(\Theta(n^3)\) 的，所以考虑优化。
不难发现 \(\log_{10}k\) 是很小的，所以考虑来枚举 \(k\)，得到新的状态转移方程：
\[ dp_{i,j} = 25 \times (\sum_{k = 0}^{\lfloor \log_{10}k \rfloor}\sum_{p = i - 10^k + 1 }^{i - 10^{k - 1}}dp_{p,p - k - 1}) \]然后最后的那个 \(\sum\) 可以用前缀和优化一下，时间复杂度为 \(\Theta(n^2\log_{10}n)\)。
Code
#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N = 3010;
int n,mod,ans;
int pt[] = {1,10,100,1000,10000};
int dp[N][N],s[N][N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int exgcd(int a,int b,int &x,int &y){
if (!b){
x = 1;
y = 0;
return a;
}
int d = exgcd(b,a % b,y,x);
y = y - a / b * x;
return d;
}
inline int get_inv(int a,int p){
int x,y;
exgcd(a,p,x,y);
return (x % mod + mod) % mod;
}
inline int sum(int l,int r,int k){
if (l > r || r < 0 || k < 0) return 0;
if (l <= 0) return s[r][k];
return ((s[r][k] - s[l - 1][k]) % mod + mod) % mod;
}
signed main(){
n = read();
mod = read();
dp[0][0] = s[0][0] = 1;
for (re int i = 1;i <= n;i++){
for (re int j = 0;j < n;j++){
for (re int k = 1;k <= 4;k++) dp[i][j] = (dp[i][j] + sum(i - pt[k] + 1,i - pt[k - 1],j - k - 1) * 25) % mod;
s[i][j] = (s[i - 1][j] + dp[i][j]) % mod;
}
}
for (re int i = 0;i < n;i++) ans = (ans + dp[n][i]) % mod;
printf("%lld",ans * get_inv(25,mod) % mod * 26 % mod);
return 0;
}