TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5410
  • 题目
  • P5410【欢乐的痛苦赛】错误的理解
    限制 : 时间限制 : - MS   空间限制 : 1048576 KB
    问题描述

    题在被nodgd做。

    nodgd正在做的这道题,给出了两个长度为 $2n$ 的序列 \(\\{a_1,a_2,\dots,a_{2n}\\},\ \\{b_1,b_2,\dots,b_{2n}\\}\) ,序列中每个数都是不超过 \(n\) 的正整数,且每个数都恰好出现了两次。

    题目曾经被nodgd理解错。

    nodgd错误的以为,题目需要计算两个序列的最长上升公共子序列的长度,以及有多少不同的最长上升公共子序列。

    两个序列的一个公共子序列可以用每个数在原序列中的下标序列来表示:

    \[ \\{i_1,i_2,\dots,i_m;\ j_1,j_2,\dots,j_m\\} \]

    其中 \(m\) 是公共子序列的长度,对于 \(k=1,2,\dots,m\) 都满足 \(a_{i_k}=b_{j_k}\) ,且下标序列单调递增,即

    \[ 1\leq i_1<i_2<\dots<i_m\leq 2n \\\\ 1\leq j_1<j_2<\dots<j_m\leq 2n \]

    两个公共子序列不同,当且仅当对应的下标序列不同。

    后来题目又被nodgd正确的理解了。

    nodgd发现自己理解错题意之后,就把这个问题作为考试题拿来恶心你。考虑到不同的最长上升公共子序列的数量可能比较多,你只需要计算出答案 \(\bmod 1,000,000,009\) 之后的结果。

    输入格式

    输入共三行。

    第一行有一个整数 \(n\) ,含义如问题描述中所述。

    第二行有 $2n$ 个整数 \(a_1,a_2,\dots,a_{2n}\) 表示第一个序列。

    第三行有 $2n$ 个整数 \(b_1,b_2,\dots,b_{2n}\) 表示第二个序列。

    输出格式

    输出共两行。

    第一行有一个整数,是这两个序列的最长上升公共子序列的长度。

    第二行有一个整数,是不同的最长上升公共子序列的数量 \(\bmod 1,000,000,009\) 后的结果。

    样例输入

    3
    2 3 1 3 1 2
    2 2 3 1 3 1

    样例输出

    2
    9

    提示

    输入输出样例1说明

    最长上升公共子序列可以是 $1,3$ 或者 $2,3$ ,长度是 $2$ 。

    形如 $1,3$ 的最长上升公共子序列有 $1$ 种,它的下标序列是

    \[ \\{3,4;4,5\\} \]

    形如 $2,3$ 的最长上升公共子序列有 $8$ 种,它们的下标序列是

    \[ \\{1,2;1,3\\} \\\\ \\{1,2;1,5\\} \\\\ \\{1,2;2,3\\} \\\\ \\{1,2;2,5\\} \\\\ \\{1,4;1,3\\} \\\\ \\{1,4;1,5\\} \\\\ \\{1,4;2,3\\} \\\\ \\{1,4;2,5\\} \]

    合计 $9$ 种不同的最长上升公共子序列。

    数据规模与约定

    前 $10\%$ 的数据, \(n\leq 5\)

    前 $30\%$ 的数据, \(n\leq 12\)

    前 $50\%$ 的数据, \(n\leq 100\) ;

    前 $70\%$ 的数据,\(n\leq 1000\) ;

    全部的测试数据, $1\leq n\leq 30000​$ 。


    来源  感谢nodgd命题