DTOJ 4751. 女装

题意

原题题目：生而为人的目的是体验生活百态，所以每个男孩的衣柜里都应该偷偷藏一套女装

由于小A女装的欲望日益强烈，并且他进队的几率日益提升，已经到了 $99.99999...（2511154个9）\%$，所以AlseoR提议准备给小A一个惊喜。机房人民集资买了 $n$ 件衣服，编号为 $1$ 的衣服是小A最喜欢的女装。

小A摆放物品时有个习惯，不喜欢打乱原先物品的位置，因此小A家的衣柜只能从两侧打开，可以从左边放衣服进去也可以从右边放衣服进去，并且会把之前已经在衣柜里的衣服往中间挤。比如衣柜里面已经有 $1,2,3$ 三件衣服了，现在从左边放一件 $4$ 号衣服进去就变成了 $4,1,2,3$，在右边放一件 $5$ 号女装就变成了$4,1,2,3,5$ 。现在AlseoR带着机房人民集资为小A买的n件衣服潜入了小A的家，将衣服按编号从小到大放进衣柜，每次可以任意选择左侧或者右侧放入。

但是小A作为一个强迫症，他希望可以存在一种方式从衣柜两侧不断取出衣服（取完为止），每次可以任意选择将左侧的衣服或者右侧的取出，第 $K$ 件可以取出女装。所以他想问问你方案的总数。由于小A不知道衣柜里面的衣服是怎么摆放的，所以他只关心取出的顺序。即对于两个方案不同，当且仅当存在一个 $x$ ,两个方案取出的第 $x$ 件衣服编号是不同的。当然这个数可能很大，所以小A决定从他最喜欢的三个数中选一个给你当模数。

题解

直观地考虑取出衣服的过程：一开始两端有一段是$n$，如果取出$n$就转化为$n-1$的问题，否则如果取出的另一端是$x$，那么$x+1,...,n$按照从里到外排列在另一端，即下一次取或者取$n$，或者取的数$<x$。于是考虑DP：设$f[i][j][k]$为$1\dots i$中后面j个数不能取（i除外），取了$k$次的方案数，答案即为 f [ n ] [ 1 ] [ k − 1 ] ∗ 2 m a x ( n − k − 1 , 0 ) f[n][1][k-1]*2^{max(n-k-1,0)} f[n][1][k−1]∗2max(n−k−1,0)。
前缀和优化转移是 O ( n 3 ) O(n^{3}) O(n3)的，但发现$f[i][j][k]$由$f[i-1][x][k-1]$转移过来，且转移过程类似于作后缀和。由此想到组合意义，画成路径可发现$f[n][1][k-1]=C(k+n-2,k-1)-C(k+n-2,n)$。
此处必须吐槽一下部分分，没有给朴素的DP应有的分，必须化成组合意义才有分，而3,4,5三个点又误导人往 O ( n 2 ) O(n^{2}) O(n2)去想（实际上是方便求组合数），令选手十分自闭（虽然本质上是我弱智，没有及时发现比较显然的转移规律）。
后面就是$exlucas$了，不会数论的我强行yy了一下，想错了好几次调了半天。大概就是把$P$唯一分解，求出 n ! % p i k i n!\% p_i^{k_i} n!%piki​​的值后$crt$合并一下。求 n ! % p i k i n!\% p_i^{k_i} n!%piki​​的时候，先把$n!$中$p$的倍数提出来，把它们各提取一个$p$后递归下去算剩下的值，剩下不是$p$的倍数的数可以按照 p k p^{k} pk分为若干段，因为这里的$p$对应的 p k p^k pk不会很大，直接预处理即可。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！