noip20d2t2
因为笨 写的详细一点。
题意
给定 n,m，对于长为 n 的排列 a,\(cnt_i=\sum_{1\leq l\leq i\leq r\leq n}[\max_{j=l}^r a_j=a_i]\)。求有多少排列 a 满足所有 \(cnt_i\) 都小于等于 m，答案对质数 p 取模。
题解
$ \text{cnt}_i $ 是 “所有包含 i 的区间 $ [l, r] $ 中，最大值为 $ a_i $ （即 M）” 的区间数量。
区间的左端点 l 可以选 $ 1 \sim i $ （共 i 种选择）;
区间的右端点 r 可以选 $ i \sim n $ （共 $ n - i + 1 $ 种选择）。
因此，满足条件的区间总数为 l 的选择数 $ \times $ r 的选择数，即： $ cnt_i = i \times (n + 1 - i) $
对于长度为 i 的排列，设全局最大值的位置为 p（ $ 1 \leq p \leq i $ ），则该位置的 $ \text{cnt}_p = p \cdot (i - p + 1) $ （左端点有 p 种选法，右端点有 $ i - p + 1 $ 种选法）。
函数 $ p \cdot (i - p + 1) $ 是关于 p 的二次函数（开口向下），其最大值出现在 $ p \approx \frac{i+1}{2} $ 时。
此时最大值为： $ \max_{p} \left( p \cdot (i - p + 1) \right) = \lceil \frac{i}{2} \rceil \cdot \left( i - \lceil \frac{i}{2} \rceil + 1 \right) $
条件 $ \lceil \frac{i}{2}\rceil \cdot (i - \lceil \frac{i}{2}\rceil + 1) \leq m $ 表示：长度为i的排列中，全局最大值位置的最大可能 $ \text{cnt} $ 不超过 m 。
根据之前的结论：若全局最大值的 $ \text{cnt} $ 不超过m，则其两侧的子排列（左侧 $ [1, p-1] $ 和右侧 $ [p+1, i] $ ）是 “天然合法” 的 —— 即子排列中所有位置的 $ \text{cnt} $ 必然都不超过 m（因为子排列的最大 $ \text{cnt} $ 小于全局最大值的 $ \text{cnt} $ ）。
由于全局最大值的最大可能 $ \text{cnt} $ 已不超过m，且两侧子排列天然合法，因此任意长度为 i 的排列都满足 “所有位置的 $ \text{cnt} $ 不超过 m”。而长度为i的排列总数为 $ i! $ ，故此时 $ f_i = i! $ 。
若全局最大值位置合法，需：从剩下的 $ n-1 $ 个数中选 i 个，排列到 “更短的子排列” 中（选法数为 $ \binom{n-1}{i} \cdot i! = \frac{(n-1)!}{(n-i)!} $ ，其中 $ \binom{n-1}{i} $ 是选数， $ i! $ 是子排列的排列方式）；剩下的 $ n-i $ 个数构成 “更长的子排列”，其合法数为 $ f_{n-i} $ （子排列的合法性与元素相对大小有关，递归求解）。
对所有可能的 “更短侧长度 i”，累加 “选数 + 子排列合法” 的情况，并乘 2（对称情形），得到： $ f_n = 2 \sum_{i=1}^{\lfloor n/2 \rfloor} \left[ i(n+1-i) \leq m \right] \cdot \frac{(n-1)!}{(n-i)!} \cdot f_{n-i} $
可以移个项。用个 \(h_i=\frac{f_i}{i!}\) 代码好看点。
https://zhengruioi.com/submission/973679
数组要开够。