Count Common Subsequence Pairs
Count the pairs (I, J) where I is a set of positions in the first string, J is a
set of positions in the second, and the two spell the SAME string. The empty pair counts.
Print the count modulo 1000000007.
ab, ab -> 4 empty, a with a, b with b, ab with ab
a, b -> 1 only the empty pair
aa, a -> 3 empty, first a with a, second a with a
## The inclusion and exclusion
dp[i][j] = the number of pairs using only the first i and first j characters
Every pair either omits position i of the first string, omits position j of the second,
or uses both. Adding dp[i-1][j] and dp[i][j-1] counts the first two families and
double counts the pairs omitting BOTH:
a[i-1] != b[j-1] -> dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
When the characters MATCH there is an extra family: any pair from dp[i-1][j-1] extended
by matching these two positions against each other. That adds dp[i-1][j-1], which cancels
the subtraction:
a[i-1] == b[j-1] -> dp[i][j] = dp[i-1][j] + dp[i][j-1]
## Why the cancellation is worth understanding
The matching case has two terms and the non-matching case has three, which is the reverse of the shape people expect from problem #237 where matching is the SIMPLER branch with a plus one.
The reason is the same as in problem 521: the subtraction and the new family are the same quantity, so they cancel exactly. Both problems are inclusion and exclusion over an interval or a grid, and in both the cancellation is what makes one branch look too short.
Being able to rederive that, rather than remembering which branch has which count of terms, is the difference between the two problems being one idea and being two formulas.
## The base row and column
dp[0][j] = 1 and dp[i][0] = 1, for every i and j: the only pair available when one
side has no characters is the empty pair.
Setting them to 0 makes every entry 0. Setting only dp[0][0] = 1 and leaving the rest of
the row and column at 0 undercounts, and the error is subtle: the answer comes out too small
by a varying amount rather than uniformly, which is harder to spot than a constant offset.
## Negatives under the modulus
The non-matching branch subtracts, so add the modulus before reducing in every language except Python. The same asymmetry as problem 521.
## Counting by position
aa against a answers 3, not 2, because the two as of the first string are different
POSITIONS and each pairs with the single a of the second. Counting distinct STRINGS would
give 2.
aa against aa answers 6 and aab against aba answers 9, both of which need the
positional reading.
## Cost
Time O(n m). Space O(m) with two rows.