AT_agc065_b.[AGC065B] Erase and Insert
省选/NOI-
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
给定一个 $ (1,2,\dots,N) $ 的排列 $ P $。另外，还有一个排列 $ Q=(1,2,\dots,N) $。
对 $ Q $ 依次进行如下操作，操作编号为 $ i=1,2,\dots,N $：
- 从 $ Q $ 中删除 $ i $，然后将 $ i $ 插入到 $ Q $ 的任意一个位置。
经过 $ N $ 次操作后，问有多少种操作方法可以使得 $ P $ 和 $ Q $ 相等。请将答案对 $ 10^9+7 $ 取模后输出。
输入格式
输入通过标准输入给出，格式如下：
$ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $
输出格式
请输出答案。
输入输出样例
输入#1
3 1 2 3
输出#1
5
输入#2
4 2 4 1 3
输出#2
11
输入#3
15 7 5 14 10 4 2 3 6 8 11 12 1 15 13 9
输出#3
306264
输入#4
30 15 19 13 11 22 27 21 25 1 12 30 28 16 26 10 14 20 2 5 7 23 4 17 6 29 3 18 9 8 24
输出#4
33525150
说明/提示
限制
- $ 1\leq N\leq 5000 $
- $ P $ 是 $ (1,2,\dots,N) $ 的一个排列
样例解释 1
例如，按照如下操作，最终 $ Q=(1,2,3) $：
- 从 $ Q=(1,2,3) $ 中删除 $ 1 $，将 $ 1 $ 插入到 $ 2,3 $ 之间。此时 $ Q=(2,1,3) $。
- 从 $ Q=(2,1,3) $ 中删除 $ 2 $，将 $ 2 $ 插入到 $ Q $ 的末尾。此时 $ Q=(1,3,2) $。
- 从 $ Q=(1,3,2) $ 中删除 $ 3 $，将 $ 3 $ 插入到 $ Q $ 的末尾。此时 $ Q=(1,2,3) $。
包括上述方法在内，使得最终 $ Q=(1,2,3) $ 的操作方法共有 $ 5 $ 种。
由 ChatGPT 4.1 翻译
输入解题思路，AI测评打分。不知道怎么写?