1. 题目

传送门= ̄ω ̄=

2. 题解

首先不难想到:
设$f[i][j][k]$为第一个字符串的前i个字符和第二个字符串的前j个字符匹配,用了k个子串时的方案数。
那么$f[i][j][k]=f[i-1][j-1][k]+f[i-1][j-1][k-1]$,$f[i-1][j-1][k]$表示不新建一个子串,$f[i-1][j-1][k-1]$表示新建一个子串
然而我们发现,这样处理第i个字符必然会被选择,也就是我们少处理了很多状态。
那么我们分情况讨论。
新建一维,状态变为4维,第4维为0或1,表示第i个字符选或者不选。
则:
1. 第i个字符不选:那上一个状态要么选择了第i-1个字符,要么没选择第i-1个字符。
2. 第i个字符要选:那上一个状态要么没选择第i-1个字符,那现在必须新建一个子串;要么选择了第i-1个字符,可以新建子串,也可以不新建。这种情况需要满足第i个字符和第j个字符相同

所以状态转移方程:
$$f[i][j][l][0]=f[i-1][j][l][0]+f[i-1][j][l][1]$$
$$f[i][j][l][1]=f[i-1][j-1][l-1][0]+f[i-1][j-1][l-1][1]+f[i-1][j-1][l][1]$$

另:注意开long long

代码: