P2516 [HAOI2010] Longest Common Subsequence

A subsequence of a character sequence is a character sequence formed by arbitrarily deleting any number of characters (possibly zero), not necessarily contiguous, from the given sequence. Let the given character sequence be $X=\{x_0,x_1,\cdots,x_{m-1}\}$, and let $Y=\{y_0,y_1,\cdots,y_{k-1}\}$ be a subsequence of $X$ if and only if there exists a strictly increasing index sequence $\{i_0,i_1,\cdots,i_{k-1}\}$ of $X$ such that for all $j=0,1,\cdots,k-1$, we have $x_{i_j}=y_j$. For example, $X=\verb!"ABCBDAB"!$, and $Y=\verb!"BCDB"!$ is a subsequence of $X$. For two given character sequences, compute the length of their longest common subsequence, and the number of longest common subsequences. Two subsequences $i$ and $j$ are different if and only if their lengths are different, or there exists $\exists k$ such that $i_k \neq j_k$.

The first line is the first character sequence, consisting of uppercase letters, ending with `.`. The number of uppercase letters does not exceed $5000$. The second line is the second character sequence, consisting of uppercase letters, ending with `.`. The number of uppercase letters does not exceed $5000$.

On the first line, output the length of the longest common subsequence of the two sequences. On the second line, output the number of all possible longest common subsequences. The answer may be large; output the answer modulo $10^{8}$.

Translated by ChatGPT 5