AGC030F
文章目录
假设存在一个$i(i\in [1,n])$满足$A_{2i-1}$与$A_{2i}$均不为$-1$。显然此时的$B_i$已经确定，所以这两个数并不会产生贡献，直接将这两个数“丢掉”即可。
由于我们只需要求出不同序列${B_i}$的数量，为了更方便求出答案，考虑进行以下钦定：
- $A_{2i}=-1$ (否则可以交换$A_{2i-1}$与$A_{2i}$)
- 如果$A_{2i-1}=A_{2i}=-1$，则$A_{2i-1}$上填的数比$A_{2i}$上填的数大。
- 令$S$为满足条件的$A_{2i-1}=A_{2i}=-1$的所有$i$的集合，假设$S={x_1,\ldots ,x_k } (x_1 < \ldots <x_k )$，则$A_{2x_1},\ldots A_{2x_k}$上填的数是递减的。
再乘上$|S|!$就是最后的答案。
考虑确定整数$2N,2N-1,\ldots 1$在${B_i}$中出现（或不出现）的位置。
然后分类讨论${B_i}$中出现整数$n$的出现有以下几类：
-
$a(n):$ $n$并没有在${A_i}$或者${B_i}$中出现
-
$a'(n): n$并没有在${B_i}$中出现，但在${A_i }$中出现过
-
$b(n):$对于所有满足$A_{2i-1}=A_{2i}=-1$的$i$，它出现在$B_i$中
-
$c_p(n):$对于满足$A_{2i-1}=p (p>n)$的$i$，它出现在$B_i$中
-
$d(n):$对于满足$A_{2i-1}\neq -1$的$i$，它出现在$B_i$中，此时$A_{2i-1}=n$
考虑使用$2N,2N-1,\ldots 1$的相对的出现顺序来表示${B_i}$
例如样例1的$(B_1,B_2,B_3)=(1,3,2)$就可以转换成$a'(6)\to a(5)\to a(4)\to d(3) \to b(2) \to d(1)$
所以说，不同的${B_i}$会产生出不同的出现顺序。因此，可以计算出与正确的${B_i }$相对应的出现序列的数量（即从有效排列${A_i}$中得到的${B_i}$）。
然后来考虑哪些会是正确的${B_i}$。
首先，$a(n)$和$a'(n)$必须出现总共正好$N$次，因为$B$的长度为$N$。
第二，如果$n$出现在${A_i}$中，那么它一定是$a'(n)$或者$c_p(n)$。类似的，如果$n$没有出现在${A_i}$中，那么它一定是$a(n),b(n)$或者$d(n)$。
最后，在产生${B_i}$的序列${A_i}$中，$b(n),c_p(n)$和$d(n)$都应该与大于$n$的数进行匹配，即$b(n)$和$d(n)$应该与满足$n' > n$的$a(n')$匹配。而$c_p(n)$应该与$a'(p)$进行匹配。且一个整数不能进行多次匹配。另一方面，如果出现的序列满足上述所有条件，我们可以看到对应与正确的${B_i}$。
令$f_{n,X,Y}$表示已经考虑了$\ge n$的数值中，其中有$X$个$a(i)$没有被选过，有$Y$个$a'(i)$没有选过的方案数。
然后考虑转移
- 若$n$在${A_i}$中：
- 如果$n$是$a'(n)$，那么它可以转移至$f_{n-1,X,Y\cup {n}}$（设这个为a式）
- 如果$n$是$d(n)$，那么它可以转移至$f_{n-1,X-1,Y}(X\geq 1)$
- 如果$n$不在${A_i}$中：
- 如果$n$是$a(n)$，那么它可以转移至$f_{n-1,X+1,Y}$
- 如果$n$是$b(n)$，那么它可以转移至$f_{n-1,X-1,Y}$
- 如果$n$是$c_p(n)$，那么它可以转移至$f_{n-1,X,p}(p\in Y)$（设这个为b式）
然后令$g(n,x,y)=\sum_{|Y|=y} f_{n,x,Y}$，可以发现a式为$(n,x,y)\to (n-1,x,y+1)$的转移，而b式为$y$个$(n,x,y)\to (n-1,x,y-1)$的转移。最后答案即为$g(0,0,0)$。
可以通过$O(n^3)$时间复杂度算出。
|
|