2016多校训练Contest5:1011 Two

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5791

题目翻译

两个序列分别长为 N , M 。求他们有多少个公共子序列(子序列可以不连续)。答案对1000000007取模

题解

其实就是最长公共子序列的变形,从求长度变成了求方案。
原来想一句话的。但是,比赛的时候傻逼了,所以题解好好写一写。
F[i][j] 表示第一个串到了第 i 位置,第二个串到了第 j 个位置,有多少个公共子序列。
如果 A[i] != B[j] 很明显 F[i][j] = F[i-1][j] + F[i][j-1] – F[i-1][j-1] 。容斥一下就好。
如果 A[i] == B[j] ,则 F[i][j] =F[i-1][j] + F[i][j-1] – F[i-1][j-1] +F[i-1][j-1] + 1 = F[i-1][j] + F[i][j-1] + 1

代码