E
先考虑对两个固定串怎么做：可以确定形成串的末尾一定是 \(a_{i}\) 或者 \(b_{j}\)，直接子序列 \(dp\) 即可：\(dp_{i,j,0/1}\) 表示只考虑 \(a\) 长度为 \(i\) 的前缀和 \(b\) 长度为 \(j\) 的前缀，\(0\) 表示形成的串以 \(a_{i}\) 结尾；\(1\) 表示形成的串以 \(b_{j}\) 结尾，方案数。转移 \(O(n^{2})\)。
那么推广到对 \(a\) 和 \(b\) 的所有 子串对 计数，显然不能枚举子串对分别计数。现在考虑：对 \(a,b\) 两个整串作 \(dp\) 后，我们可以得到哪些 子串对 的答案？实际上，我们得到了所有 必须以 \(a[1],b[1]\) 开头，以任意 \(a[i]\) 和 \(b[j]\) 结尾 的 子串对 的方案数 —— 对应于 \(dp\) 状态的每个 \(dp_{i,j}\)。也就是说，目前得到了 左端点固定为开头，右端点任意 的所有子区间的答案。如何扩展到 左端点任意，右端点任意 的情况呢？
暴力枚举左端点对显然是不可取的。考虑上述 \(dp\) 的转移过程：不难发现，转移式与当前串的左端点取什么是没有关系的，只和当前位置和前一个位置相关。这个时候，思考一下多源 \(bfs\)：存在多个起点时，可以直接将所有起点先放进队列，然后 \(bfs\)，转移过程只和钦定的通行方式有关；最终就可以求得对于所有位置，从任意起点出发的最短路。仔细想一下二者之间的关系，发现：所有可能的左端点对 \((l_{a},l_{b})\) 可以看作是多源 \(bfs\) 的多个起点；并且转移是固定的，和起点的位置无关。因此可以考虑对上述 \(dp\) 转移作类似多源 \(bfs\) 的优化：预先初始化好所有左端点对的dp状态，再直接对整体做一次转移，最终得到的 \(dp_{i,j}\) 便表示 \(a,b\) 的 左端点任意，右端点分别为 \(i, j\) 的所有区间的答案，对所有 \(dp_{i,j}\) 作和即为所求。
需要额外注意的地方：题目明确要求 \(a,b\) 中的子串均非空，但初始化时包含了 \(a,b\) 某一个是空串。因此需要考虑分别去除掉 \(a\)空\(b\)非空 和 \(b\)空\(a\)非空 的合法情况。二者均可 \(O(n^{2})\) 求得。具体细节见代码。
code