#P11992. [2024年联测]排列

    ID: 11142 传统题 1500ms 256MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>组合数学图论动态规划贪心CF2200计数DP数学构造

[2024年联测]排列

排列(perm)

【题目描述】

下文中「排列」均指 11 到nn的排列。

两个排列 A,BA,B 保证 ∀i\forall i, Ai≠BiA_{i}\ne B_{i}。求有多少个排列CC 满足∀i,Ci≠Ai,Ci≠Bi\forall i,C_{i}\ne A_{i},C_{i}\ne B_{i}。对 10000000071000000007 取模。

【输入格式】

从标准输入读入。

第一行一个正整数TT表示数据组数。

对于每组数据,三行,分别为n,A,Bn,A,B。

【输出格式】

输出到标准输出。

对于每组数据,一行一个整数表示答案。

【样例 1 输入】

1
4
2 4 1 3
1 3 2 4

【样例 1 输出】

4

【样例 1 解释】

合法的排列是 {3,1,4,2},{3,2,4,1},{4,1,3,2},{4,2,3,1}\{3,1,4,2\},\{3,2,4,1\},\{4,1,3,2\},\{4,2,3,1\}。

【补充样例 2】

1
2
1 2
2 1
0

原赛样例 2 至 8 引用的选手附件缺失。

【数据范围】

对于全部的数据,1≤T≤10,2≤n≤1000,Ai≠Bi1\le T\le 10,2\le n\le 1000,A_{i}\ne B_{i}。

子任务编号 分值 n≤n\le 特殊限制 子任务依赖
11 22 1010
22 55 2020 11
33 1313 5050 22
44 1919 300300 33
5 7 Ai=B(i mod n)+1A_i=B_{(i\bmod n)+1}
6 ∃k∣n, Bi=Ai−1+k[i mod k=1]\exists k\mid n,\ B_i=A_{i-1+k[i\bmod k=1]}
77 4747 4,5,64,5,6