有上限排列计数 笔记

给定排列 $a_{1\dots n}$ 与 $l_{1\dots n}$，将 $a$ 重排为 $b_{1\dots n}$，使得 $\mathrm{\forall }i,b_i\le l_i$，求方案数。

考虑将 $a$ 从大到小排序，对于 $a_1$，它可以去 $l_i$ 满足 $a_1\le l_i$ 的地方，即记 $c(i)=\sum _j[l_j\ge i]$，$a_1$ 能去 $c(a_1)$ 个地方。

考虑 $a_2$，显然他能去的地方包含 $a_1$ 能去的地方，即 $c(a_2)-1$。

以此类推，答案为

$$\prod (c(a_i)-i+1)$$