题在被nodgd做.
题目曾经被nodgd理解错.
nodgd错误的以为,题目需要计算两个序列的最长上升公共子序列的长度,以及有多少不同的最长上升公共子序列.
两个序列的一个公共子序列可以用每个数在原序列中的下标序列来表示:
两个公共子序列不同,当且仅当对应的下标序列不同.
后来题目又被nodgd正确的理解了.
nodgd发现自己理解错题意之后,就把这个问题作为考试题拿来恶心你.考虑到不同的最长上升公共子序列的数量可能比较多,你只需要计算出答案 \(\bmod 1000000009\) 之后的结果.
输入共三行.
输出共两行.
第一行有一个整数,是这两个序列的最长上升公共子序列的长度.