自动搬运

查看原文

来自洛谷，原作者为

	Little09 「按照我们原来的期待 去证明我们的未来」

搬运于2025-08-24 22:13:30，当前版本为作者最后更新于2020-03-29 12:10:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一道挺好的dp题，我的方法会理解起来稍微简单点。

题目大意就不赘述了，我们直接考虑状态。

令$f[i][j][k][l]$表示选$i$组{},$j$组[],$k$组()且深度为$l$的组合有几种。但是我们发现这样对于S=AB的状态转移是很难实现的。因为AB的深度都不知道，需要依次枚举。

我们可以考虑微调状态，令$f[i][j][k][l]$表示选$i$组{},$j$组[],$k$组()且深度小于等于$l$的组合有几种。那么这样的话，状态转移貌似就容易实现一点。

但是还有问题：对于一些复杂的SS串，可能会有不止一种分法使它分成AB的形式。

举个具体的例子：枚举A为串 $()[]$ ，B为串 $[()]$ 时，组合为 $()[][()]$，但是枚举A为串$()$，B为串$[][()]$时，组合也为$()[][()]$。这样就重复了。

所以有这样神奇的转移法出现了：对于每个非空SS串，有且仅有一种分法：找到两个SS串A,B，使得S=(A)B或[A]B或{A}B

（证明应该很显然吧）

所以这题就基本完结了。转移方程如下：

最后还有几个细节稍微说一下：

1.要预处理$f[0][0][0][i]=0$，因为可以进行转移的是非空串

2.当输入d=0时，输出特判。其余情况，输出$f[a][b][c][d]-f[a][b][c][d-1]$

3.$f[a][b][c][d]-f[a][b][c][d-1]$由于取过模，可能是负数，处理一下就好

4.题目描述里有3组样例不要错过

代码应该不用放了吧qwq