题解 P3176 【[HAOI2015]数字串拆分】

水题解……

话说这道题做得我有点懵，感觉完全是按照学长思路来的说

\(first\)

首先要搞清楚题目意思，没错，这就是第一步

话说我谷的题面有点小锅，对于\(f_4=5\land m=2\)的\(5\)种拆分方法应当是

没错，题意确实没错，是用\(1-m\)中的自然数进行数字拆分，并且是数字顺序不同也要算一种的拆分方式，于是可以乖乖考虑\(dp\)了

会发现，对于一个数字\(p\)，有

于是可以发现以上的\(m\)中拆分中，第\(i\)种拆分贡献的种类数为\(f_{p-i}\)，至于每一种为什么不用把交换位置的情况进行计算，可以手玩例子发现所有方案数已经全部算入，再交换位置算会算重（这就是为什么排列组合总是容易算错的原因吧）

于是有了第一个结论：

这下应该有点思路了——这题考的是矩阵

\(second\)

接下来看\(g\)，先给\(g_i\)换个定义：字符串从第\(1\)位\(dp\)到第\(i\)位的答案，也就是说，我们要求的是\(g_n(n=strlen(S))\)

由于上面的第一结论，我们发现可以将\(f\)用矩阵表示

设转移矩阵为\(A\)，那么\(g_i=A^{a_1+a_2+…+a_k}=A^{a_1}* A^{a_2}* …* A^{a_k}\)（这里的\(a_k\)就是\(1\)到\(i\)拆出来的一个个数）

于是再分配律走一波发现\(g_i=\sum_{j=0}^{i-1}g_j* A^{S_{(j+1)…i}}\)，而关于这个东西\(A^{S_{(j+1)…i}}\)，我们可以先预处理好\(A_{i,j}\)表示\(jei(\text{也就是}j* 10^i)\)的转移矩阵，预处理可以通过我们得到的第一个结论进行处理

于是\(g_i\)也矩阵跑一波(md矩阵)

\(third\)

核心部分就是上面这些了，最后所求的自然是\(g_n\)，而\(ans\)位置\((1,m)\)

剩下细节可以看代码（代码中用的\(f\)代替的文中的\(g\)）：

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

const int mod=998244353;

char ch[501];
int n,m;

struct node
{
	int a[6][6];
}f[501],A[501][10],zero;

node operator * (node x,node y)
{
	node tmp=zero;
	for(register int i=1;i<=m;++i)
		for(register int j=1;j<=m;++j)
			for(register int k=1;k<=m;++k)
				(tmp.a[i][j]+=1ll*x.a[i][k]*y.a[k][j]%mod)%=mod;
	return tmp;
}
node operator + (node x,node y)
{
	node tmp=zero;
	for(register int i=1;i<=m;++i)
		for(register int j=1;j<=m;++j)
			tmp.a[i][j]=(x.a[i][j]+y.a[i][j])%mod;
	return tmp;
}

int main()
{
	cin>>ch+1>>m;
	n=strlen(ch+1);
	for(register int i=1;i<=m;++i)
		for(register int j=1;j<=m;++j)
			zero.a[i][j]=0;
	for(register int i=1;i<=m;++i)
		A[0][0].a[i][i]=A[0][1].a[i][m]=1;
	for(register int i=1;i<m;++i)
		A[0][1].a[i+1][i]=1;
	for(register int i=2;i<=9;++i)
		A[0][i]=A[0][i-1]*A[0][1];
	for(register int i=1;i<=n;++i)
	{
		A[i][0]=A[0][0];
		A[i][1]=A[i-1][9]*A[i-1][1];
		for(register int j=2;j<=9;++j)
			A[i][j]=A[i][j-1]*A[i][1];
	}
	f[0].a[1][m]=1;
	for(register int i=1;i<=n;++i)
	{
		node tmp=A[0][ch[i]-‘0‘];
		for(register int j=i-1;~j;--j)
		{
			f[i]=f[i]+(f[j]*tmp);
			if(j) tmp=A[i-j][ch[j]-‘0‘]*tmp;
		}
	}
	cout<<f[n].a[1][m]<<endl;
	return 0;
}

题解 P3176 【[HAOI2015]数字串拆分】

原文：https://www.cnblogs.com/ALANALLEN21LOVE28/p/12675369.html