自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:46:08，当前版本为作者最后更新于2021-03-13 11:39:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3176 [HAOI2015]数字串拆分

题意简述：定义 $f(s)$ 为将 $s$ 拆分成若干个不大于 $m$ 个数的方案数。给出数字字符串 $t$，求 $g(t)=\sum f(x)$，其中 $x$ 为将 $t$ 分割成若干个数后它们的和。例如 $t=\texttt{12}$ 时，答案为 $f(1+2)+f(12)$。

本文节选自 DP 大锅乱炖 IV.

注意到 $m$ 的范围很小，只有 $5$，所以 $f(s)$ 可以用矩阵快速幂 $m^3\log s$ 计算（基本操作）。记转移矩阵为 $G$，那么答案即为 $(\sum G^x)_{0,0}$。我们记 $d_i$ 为 $g'(t[1:i])=\sum G^x$（可以和上面 $g(s)$ 的柿子对比一下，$g$ 是数值，$g'$ 是矩阵），则答案为 $(d_n)_{0,0}$。

不难求出转移方程 $d_i=\sum_{j=0}^{i-1}d_j\times f(t[j+1:i])$。因为 $t[j+1:i]$ 会很大（达到 $10^n$），所以快速幂的时候需要对指数高精（矩阵没有费马小定理！）。因此，这样的时间复杂度为 $\mathcal{O}(n^3m^3)$，无法承受。

注意到 $f(t)=G^t=\prod_i G^{10^{|t|-i}t_i}$，那么我们可以预处理出形如 $G^{c\times 10^k}\ (1\leq c<10,1\leq k\leq n)$ 的矩阵。然后记 $D_{l,r}$ 为 $f(t[l:r])$，那么它可以由 $D_{l+1,r}\times G^{10^{r-l}t_{l}}$ 转移过来。$nm^3|\Sigma|+n^2m^3$ 预处理后可以 $n^2m^3$ DP（$d_i=\sum_{j=0}^{i-1} d_jD_{j+1,i}$）。可以通过本题。

/*
	Powered by C++11.
	Author : Alex_Wei.
*/

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize(3)
//#define int long long

using ll = long long;
#define mem(x,v) memset(x,v,sizeof(x))

const int N=500+5;
const int M=5;
const int mod=998244353;

int n,m;
char s[N];
void add(int &x,ll y){
	x+=y%mod;
	if(x>mod)x-=mod;
}

struct mat{
	int a[M][M];
	friend mat operator * (mat x,mat y){
		mat z; mem(z.a,0);
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				for(int k=0;k<m;k++)
					add(z.a[i][j],1ll*x.a[i][k]*y.a[k][j]);
		return z;
	}
	friend mat operator + (mat x,mat y){
		mat z; mem(z.a,0);
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				add(z.a[i][j],x.a[i][j]+y.a[i][j]);
		return z;
	}
}base,f[N],c[N][N],d[N][10];

mat ksm(mat a,int b){
	mat x; mem(x.a,0);
	for(int i=0;i<m;i++)x.a[i][i]=1;
	while(b){
		if(b&1)x=x*a;
		a=a*a,b>>=1;
	} return x;
}

int main(){
	scanf("%s%d",s+1,&m),n=strlen(s+1),f[0].a[0][0]=1;
	for(int i=0;i<m;i++)base.a[i][0]=1;
	for(int i=1;i<m;i++)base.a[i-1][i]=1;
	for(int i=0;i<10;i++){
		d[0][i]=ksm(base,i);
		for(int j=1;j<=n;j++)d[j][i]=ksm(d[j-1][i],10);
	} for(int r=n;r;r--)
		for(int l=r;l;l--)
			if(l==r)c[l][r]=d[0][s[r]-'0'];
			else c[l][r]=c[l+1][r]*d[r-l][s[l]-'0'];
	for(int i=1;i<=n;i++)
		for(int j=0;j<i;j++)
			f[i]=f[i]+f[j]*c[j+1][i];
	cout<<f[n].a[0][0]<<endl;
	return 0;
}